#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using vi = vector<int>;
struct segtree
{
int l;
int r;
int v = 0;
segtree* left = NULL;
segtree* right = NULL;
segtree()
{
;
}
segtree(int L, int R)
{
l = L;
r = R;
if(l == r) return;
int m = (l+r)/2;
left = new segtree(l, m);
right = new segtree(m+1, r);
}
segtree(int L, int R, int V, segtree* LEFT, segtree* RIGHT)
{
l = L, r = R, v = V, left = LEFT, right = RIGHT;
}
int rangesum(int L, int R)
{
if(R < l || r < L) return 0;
else if(L <= l && r <= R) return v;
else return left->rangesum(L, R) + right->rangesum(L, R);
}
segtree* add(int I, int V)
{
if(I < l || r < I) return this;
else if(l == r) return new segtree{l, r, v+V, NULL, NULL};
else
{
segtree* new_left = left->add(I, V);
segtree* new_right = right->add(I, V);
return new segtree(l, r, v+V, new_left, new_right);
}
}
};
const int mx = 200'000;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, q;
cin >> n >> q;
segtree* S[1+mx+1];
S[mx+1] = new segtree(1, n);
vi p(1+n);
vi occ[1+mx];
for(int i = 1; i <= n; i++)
{
cin >> p[i];
occ[p[i]].push_back(i);
}
for(int v = mx; v >= 0; v--)
{
S[v] = S[v+1];
for(int i : occ[v])
S[v] = S[v]->add(i, 1);
}
for(int j = 1; j <= q; j++)
{
int l, r;
cin >> l >> r;
int lo = 0;
int hi = mx;
while(lo != hi)
{
int mid = (lo+hi)/2 + 1;
if(S[mid]->rangesum(l, r) >= mid)
lo = mid;
else
hi = mid-1;
}
cout << lo << '\n';
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
7116 KB |
Output is correct |
2 |
Correct |
7 ms |
7116 KB |
Output is correct |
3 |
Correct |
7 ms |
7116 KB |
Output is correct |
4 |
Correct |
7 ms |
7116 KB |
Output is correct |
5 |
Correct |
7 ms |
7116 KB |
Output is correct |
6 |
Correct |
8 ms |
7084 KB |
Output is correct |
7 |
Correct |
8 ms |
7116 KB |
Output is correct |
8 |
Correct |
8 ms |
7220 KB |
Output is correct |
9 |
Correct |
7 ms |
7116 KB |
Output is correct |
10 |
Correct |
8 ms |
7116 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
7116 KB |
Output is correct |
2 |
Correct |
7 ms |
7116 KB |
Output is correct |
3 |
Correct |
7 ms |
7116 KB |
Output is correct |
4 |
Correct |
7 ms |
7116 KB |
Output is correct |
5 |
Correct |
7 ms |
7116 KB |
Output is correct |
6 |
Correct |
8 ms |
7084 KB |
Output is correct |
7 |
Correct |
8 ms |
7116 KB |
Output is correct |
8 |
Correct |
8 ms |
7220 KB |
Output is correct |
9 |
Correct |
7 ms |
7116 KB |
Output is correct |
10 |
Correct |
8 ms |
7116 KB |
Output is correct |
11 |
Correct |
311 ms |
52652 KB |
Output is correct |
12 |
Correct |
328 ms |
52756 KB |
Output is correct |
13 |
Correct |
347 ms |
52708 KB |
Output is correct |
14 |
Correct |
352 ms |
52664 KB |
Output is correct |
15 |
Correct |
339 ms |
52676 KB |
Output is correct |
16 |
Correct |
339 ms |
52680 KB |
Output is correct |
17 |
Correct |
345 ms |
52776 KB |
Output is correct |
18 |
Correct |
336 ms |
52708 KB |
Output is correct |
19 |
Correct |
353 ms |
52668 KB |
Output is correct |
20 |
Correct |
326 ms |
52648 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
7116 KB |
Output is correct |
2 |
Correct |
7 ms |
7116 KB |
Output is correct |
3 |
Correct |
7 ms |
7116 KB |
Output is correct |
4 |
Correct |
7 ms |
7116 KB |
Output is correct |
5 |
Correct |
7 ms |
7116 KB |
Output is correct |
6 |
Correct |
8 ms |
7084 KB |
Output is correct |
7 |
Correct |
8 ms |
7116 KB |
Output is correct |
8 |
Correct |
8 ms |
7220 KB |
Output is correct |
9 |
Correct |
7 ms |
7116 KB |
Output is correct |
10 |
Correct |
8 ms |
7116 KB |
Output is correct |
11 |
Correct |
311 ms |
52652 KB |
Output is correct |
12 |
Correct |
328 ms |
52756 KB |
Output is correct |
13 |
Correct |
347 ms |
52708 KB |
Output is correct |
14 |
Correct |
352 ms |
52664 KB |
Output is correct |
15 |
Correct |
339 ms |
52676 KB |
Output is correct |
16 |
Correct |
339 ms |
52680 KB |
Output is correct |
17 |
Correct |
345 ms |
52776 KB |
Output is correct |
18 |
Correct |
336 ms |
52708 KB |
Output is correct |
19 |
Correct |
353 ms |
52668 KB |
Output is correct |
20 |
Correct |
326 ms |
52648 KB |
Output is correct |
21 |
Correct |
2091 ms |
210524 KB |
Output is correct |
22 |
Correct |
2065 ms |
210564 KB |
Output is correct |
23 |
Correct |
2266 ms |
210648 KB |
Output is correct |
24 |
Correct |
2159 ms |
210532 KB |
Output is correct |
25 |
Correct |
2150 ms |
210568 KB |
Output is correct |
26 |
Correct |
2086 ms |
210552 KB |
Output is correct |
27 |
Correct |
2079 ms |
210552 KB |
Output is correct |
28 |
Correct |
2227 ms |
210608 KB |
Output is correct |
29 |
Correct |
2144 ms |
210452 KB |
Output is correct |
30 |
Correct |
2056 ms |
210468 KB |
Output is correct |