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 |