#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9 + 7;
const ll LOGN = 20;
const ll MAXN = 2e5 + 5;
const ll SQ = 500;
vector<pair<pair<int,int>,int>> query;
vector<int> A;
int ans[MAXN], suff[MAXN], res = 1, cnt = 1;
void insert(int x) {
suff[A[x]]++;
if (A[x] >= res)
cnt++;
if (cnt - suff[res] > res) {
cnt -= suff[res];
res++;
}
}
void omit(int x) {
suff[A[x]]--;
if (A[x] >= res)
cnt--;
if (cnt < res) {
res--;
cnt += suff[res];
}
}
int main() {
fast
int N, Q;
cin >> N >> Q;
A = vector<int>(N+1);
query = vector<pair<pair<int,int>,int>>(Q);
for (int i = 1; i <= N; i++)
cin >> A[i];
for (int i = 0; i < Q; i++) {
cin >> query[i].f.f >> query[i].f.s;
query[i].s = i;
}
sort(query.begin(), query.end(), [&](pair<pair<int,int>,int> a, pair<pair<int,int>,int> b) {
return make_pair(a.f.f / SQ, a.f.s) < make_pair(b.f.f / SQ, b.f.s);
});
int l = 1, r = 1;
suff[A[1]]++;
for (auto u : query) {
int new_l = u.f.f;
int new_r = u.f.s;
while (new_l < l) {
l--;
insert(l);
}
while (new_r > r) {
r++;
insert(r);
}
while (new_l > l) {
omit(l);
l++;
}
while (new_r < r) {
omit(r);
r--;
}
ans[u.s] = res;
}
for (int i = 0; i < Q; i++)
cout << ans[i] << "\n";
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
344 KB |
Output is correct |
3 |
Correct |
1 ms |
344 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
344 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
344 KB |
Output is correct |
8 |
Correct |
1 ms |
344 KB |
Output is correct |
9 |
Correct |
1 ms |
344 KB |
Output is correct |
10 |
Correct |
1 ms |
344 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
344 KB |
Output is correct |
3 |
Correct |
1 ms |
344 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
344 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
344 KB |
Output is correct |
8 |
Correct |
1 ms |
344 KB |
Output is correct |
9 |
Correct |
1 ms |
344 KB |
Output is correct |
10 |
Correct |
1 ms |
344 KB |
Output is correct |
11 |
Correct |
81 ms |
1872 KB |
Output is correct |
12 |
Correct |
81 ms |
1872 KB |
Output is correct |
13 |
Correct |
85 ms |
1884 KB |
Output is correct |
14 |
Correct |
82 ms |
1888 KB |
Output is correct |
15 |
Correct |
83 ms |
1872 KB |
Output is correct |
16 |
Correct |
82 ms |
1872 KB |
Output is correct |
17 |
Correct |
82 ms |
1872 KB |
Output is correct |
18 |
Correct |
81 ms |
1892 KB |
Output is correct |
19 |
Correct |
81 ms |
1884 KB |
Output is correct |
20 |
Correct |
81 ms |
1872 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
344 KB |
Output is correct |
3 |
Correct |
1 ms |
344 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
344 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
344 KB |
Output is correct |
8 |
Correct |
1 ms |
344 KB |
Output is correct |
9 |
Correct |
1 ms |
344 KB |
Output is correct |
10 |
Correct |
1 ms |
344 KB |
Output is correct |
11 |
Correct |
81 ms |
1872 KB |
Output is correct |
12 |
Correct |
81 ms |
1872 KB |
Output is correct |
13 |
Correct |
85 ms |
1884 KB |
Output is correct |
14 |
Correct |
82 ms |
1888 KB |
Output is correct |
15 |
Correct |
83 ms |
1872 KB |
Output is correct |
16 |
Correct |
82 ms |
1872 KB |
Output is correct |
17 |
Correct |
82 ms |
1872 KB |
Output is correct |
18 |
Correct |
81 ms |
1892 KB |
Output is correct |
19 |
Correct |
81 ms |
1884 KB |
Output is correct |
20 |
Correct |
81 ms |
1872 KB |
Output is correct |
21 |
Correct |
353 ms |
6480 KB |
Output is correct |
22 |
Correct |
356 ms |
9864 KB |
Output is correct |
23 |
Correct |
355 ms |
9808 KB |
Output is correct |
24 |
Correct |
355 ms |
9808 KB |
Output is correct |
25 |
Correct |
355 ms |
9808 KB |
Output is correct |
26 |
Correct |
361 ms |
9972 KB |
Output is correct |
27 |
Correct |
356 ms |
9976 KB |
Output is correct |
28 |
Correct |
353 ms |
9808 KB |
Output is correct |
29 |
Correct |
355 ms |
9868 KB |
Output is correct |
30 |
Correct |
356 ms |
9868 KB |
Output is correct |