5723 2023. 09. 10 01:32:49 TomaSajt Legmesszebbi rossz sorrendű (35 pont) cpp17 Elfogadva 35/35 90ms 30180 KiB
#include <bits/stdc++.h>
using namespace std;

struct seg_tree {
  int val{INT_MAX};
  seg_tree *lc{}, *rc{};
  int lx, rx;

  seg_tree(int lx, int rx)
      : lx{lx}, rx{rx} {}

  void ensure_children_exist() {
    int m = (lx + rx) / 2;
    if (!lc) lc = new seg_tree(lx, m);
    if (!rc) rc = new seg_tree(m, rx);
  }

  int get(int l, int r) {
    if (rx <= l || r <= lx) return INT_MAX;
    if (l <= lx && rx <= r) return val;
    ensure_children_exist();
    return min(lc->get(l, r), rc->get(l, r));
  }

  void set(int i, int v) {
    if (lx + 1 == rx) {
      val = v;
      return;
    }
    ensure_children_exist();
    if (i < lc->rx) lc->set(i, v);
    else rc->set(i, v);
    val = min(lc->val, rc->val);
  }
};

int main() {
  cin.tie(0), cin.sync_with_stdio(0);

  int n;
  cin >> n;

  seg_tree st(-100000, 100001);

  int bestI = -1, bestJ = 0;
  for (int i = 0; i < n; i++) {
    int vi;
    cin >> vi;

    int j = st.get(vi + 1, 100001);

    if (st.get(vi, vi + 1) == INT_MAX) st.set(vi, i); // only set if this was the first occurance of vi

    if (j == INT_MAX) continue;
    int d = i - j;
    int bestD = bestI - bestJ;
    if (d > bestD || (d == bestD && j < bestJ)) {
      bestI = i;
      bestJ = j;
    }
  }

  if (bestI == -1) {
    cout << "-1";
    return 0;
  }

  cout << bestJ + 1 << ' ' << bestI + 1;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 35/35
1 Elfogadva 0/0 3ms 2048 KiB
2 Elfogadva 0/0 90ms 21560 KiB
3 Elfogadva 1/1 3ms 2992 KiB
4 Elfogadva 1/1 3ms 3208 KiB
5 Elfogadva 1/1 3ms 3428 KiB
6 Elfogadva 1/1 3ms 3640 KiB
7 Elfogadva 1/1 3ms 4020 KiB
8 Elfogadva 1/1 4ms 4804 KiB
9 Elfogadva 1/1 4ms 5752 KiB
10 Elfogadva 1/1 6ms 6464 KiB
11 Elfogadva 1/1 8ms 8620 KiB
12 Elfogadva 2/2 29ms 12000 KiB
13 Elfogadva 2/2 34ms 13516 KiB
14 Elfogadva 2/2 35ms 14304 KiB
15 Elfogadva 2/2 23ms 11224 KiB
16 Elfogadva 2/2 37ms 15116 KiB
17 Elfogadva 2/2 64ms 19960 KiB
18 Elfogadva 2/2 72ms 22188 KiB
19 Elfogadva 2/2 79ms 24436 KiB
20 Elfogadva 2/2 81ms 25480 KiB
21 Elfogadva 2/2 89ms 27732 KiB
22 Elfogadva 2/2 90ms 28620 KiB
23 Elfogadva 2/2 68ms 29312 KiB
24 Elfogadva 2/2 68ms 30180 KiB