4918 | 2023. 04. 07 01:03:39 | TomaSajt | Legmesszebbi rossz sorrendű (35 pont) | cpp17 | Accepted 35/35 | 86ms | 23676 KiB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
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);
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;
return 0;
}
Subtask | Sum | Test | Verdict | Time | Memory | ||
---|---|---|---|---|---|---|---|
base | 35/35 | ||||||
1 | Accepted | 0/0 | 3ms | 1896 KiB | |||
2 | Accepted | 0/0 | 86ms | 20716 KiB | |||
3 | Accepted | 1/1 | 3ms | 2372 KiB | |||
4 | Accepted | 1/1 | 2ms | 2396 KiB | |||
5 | Accepted | 1/1 | 3ms | 2528 KiB | |||
6 | Accepted | 1/1 | 3ms | 2864 KiB | |||
7 | Accepted | 1/1 | 3ms | 3164 KiB | |||
8 | Accepted | 1/1 | 4ms | 3624 KiB | |||
9 | Accepted | 1/1 | 4ms | 4604 KiB | |||
10 | Accepted | 1/1 | 6ms | 5688 KiB | |||
11 | Accepted | 1/1 | 8ms | 7492 KiB | |||
12 | Accepted | 2/2 | 28ms | 10960 KiB | |||
13 | Accepted | 2/2 | 32ms | 11888 KiB | |||
14 | Accepted | 2/2 | 34ms | 12500 KiB | |||
15 | Accepted | 2/2 | 21ms | 9424 KiB | |||
16 | Accepted | 2/2 | 35ms | 13236 KiB | |||
17 | Accepted | 2/2 | 61ms | 17784 KiB | |||
18 | Accepted | 2/2 | 68ms | 19416 KiB | |||
19 | Accepted | 2/2 | 76ms | 20940 KiB | |||
20 | Accepted | 2/2 | 79ms | 21464 KiB | |||
21 | Accepted | 2/2 | 85ms | 23196 KiB | |||
22 | Accepted | 2/2 | 85ms | 23376 KiB | |||
23 | Accepted | 2/2 | 65ms | 23436 KiB | |||
24 | Accepted | 2/2 | 65ms | 23676 KiB |