4914 | 2023. 04. 06 23:21:57 | TomaSajt | Legmesszebbi rossz sorrendű (35 pont) | cpp17 | Elfogadva 35/35 | 64ms | 10056 KiB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct segtree {
int size;
vector<int> v;
segtree(int size) : size(size), v(size * 4, INT_MAX) {}
void set(int i, int val) { set(i, val, 0, 0, size); }
void set(int i, int val, int x, int lx, int rx) {
if (lx + 1 == rx) {
v[x] = val;
return;
}
int m = (lx + rx) / 2;
if (i < m)
set(i, val, 2 * x + 1, lx, m);
else
set(i, val, 2 * x + 2, m, rx);
v[x] = min(v[2 * x + 1], v[2 * x + 2]);
}
int get(int l, int r) { return get(l, r, 0, 0, size); }
int get(int l, int r, int x, int lx, int rx) {
if (rx <= l || r <= lx)
return INT_MAX;
if (l <= lx && rx <= r)
return v[x];
int m = (lx + rx) / 2;
return min(get(l, r, 2 * x + 1, lx, m), get(l, r, 2 * x + 2, m, rx));
}
};
int main() {
cin.tie(0), cin.sync_with_stdio(0);
int n;
cin >> n;
segtree st(200001);
int bestDist = -1;
set<pair<int, int>> sols;
for (int i = 0; i < n; i++) {
int vi;
cin >> vi;
vi += 100000;
int j = st.get(vi + 1, 200001);
if (st.get(vi, vi + 1) == INT_MAX)
st.set(vi, i);
if (j == INT_MAX)
continue;
int dist = i - j + 1;
if (dist >= bestDist) {
if (dist != bestDist)
sols.clear();
bestDist = dist;
sols.insert({j, i});
}
}
if (sols.size() == 0) {
cout << "-1";
return 0;
}
cout << sols.begin()->first + 1 << ' ' << sols.begin()->second + 1;
return 0;
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 35/35 | ||||||
1 | Elfogadva | 0/0 | 4ms | 8116 KiB | |||
2 | Elfogadva | 0/0 | 64ms | 8372 KiB | |||
3 | Elfogadva | 1/1 | 4ms | 8292 KiB | |||
4 | Elfogadva | 1/1 | 4ms | 8296 KiB | |||
5 | Elfogadva | 1/1 | 4ms | 8548 KiB | |||
6 | Elfogadva | 1/1 | 4ms | 8764 KiB | |||
7 | Elfogadva | 1/1 | 4ms | 8976 KiB | |||
8 | Elfogadva | 1/1 | 6ms | 8928 KiB | |||
9 | Elfogadva | 1/1 | 6ms | 8948 KiB | |||
10 | Elfogadva | 1/1 | 7ms | 8948 KiB | |||
11 | Elfogadva | 1/1 | 8ms | 8948 KiB | |||
12 | Elfogadva | 2/2 | 26ms | 9228 KiB | |||
13 | Elfogadva | 2/2 | 28ms | 9188 KiB | |||
14 | Elfogadva | 2/2 | 29ms | 9144 KiB | |||
15 | Elfogadva | 2/2 | 20ms | 9288 KiB | |||
16 | Elfogadva | 2/2 | 30ms | 9396 KiB | |||
17 | Elfogadva | 2/2 | 48ms | 9632 KiB | |||
18 | Elfogadva | 2/2 | 54ms | 9760 KiB | |||
19 | Elfogadva | 2/2 | 57ms | 9716 KiB | |||
20 | Elfogadva | 2/2 | 59ms | 9716 KiB | |||
21 | Elfogadva | 2/2 | 64ms | 9844 KiB | |||
22 | Elfogadva | 2/2 | 64ms | 10036 KiB | |||
23 | Elfogadva | 2/2 | 52ms | 10056 KiB | |||
24 | Elfogadva | 2/2 | 54ms | 9988 KiB |