#include <bits/stdc++.h>
#define int long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int N = 2e5+5;
int k, arr[N], cnt[N], block[N], ans[N], l = 1, r = 0;
struct query{
int l, r, idx;
bool operator < (query b){
if(l/k==b.l/k){
if((l/k)&1) return r/k < b.r/k;
return r/k > b.r/k;
}else{
return l/k < b.l/k;
}
};
};
void add(int idx){
cnt[arr[idx]]++;
block[arr[idx]/k]++;
}
void del(int idx){
cnt[arr[idx]]--;
block[arr[idx]/k]--;
}
int getans(){
int now = 0;
for(int i = N/k;~i;i--){
if(now+block[i]>=i*k){
for(int j = (i+1)*k-1;j>=i*k;j--){
now += cnt[j];
if(now >= j){
return j;
}
}
}
now += block[i];
}
return 0;
}
signed main(){
fastio
int n,q;
cin >> n >> q;
k = sqrt(n);
for(int i = 1;i <= n;i++){
cin >> arr[i];
}
vector<query> Q;
for(int i = 0;i < q;i++){
int l,r;
cin >> l >> r;
Q.push_back({l,r,i});
}
sort(Q.begin(),Q.end());
for(auto q : Q){
while(l < q.l) del(l++);
while(l > q.l) add(--l);
while(r < q.r) add(++r);
while(r > q.r) del(r--);
ans[q.idx] = getans();
}
for(int i = 0;i < q;i++){
cout << ans[i] << "\n";
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
332 KB |
Output is correct |
2 |
Correct |
6 ms |
332 KB |
Output is correct |
3 |
Correct |
9 ms |
436 KB |
Output is correct |
4 |
Correct |
10 ms |
332 KB |
Output is correct |
5 |
Correct |
6 ms |
428 KB |
Output is correct |
6 |
Correct |
6 ms |
332 KB |
Output is correct |
7 |
Correct |
6 ms |
332 KB |
Output is correct |
8 |
Correct |
6 ms |
332 KB |
Output is correct |
9 |
Correct |
6 ms |
332 KB |
Output is correct |
10 |
Correct |
7 ms |
332 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
332 KB |
Output is correct |
2 |
Correct |
6 ms |
332 KB |
Output is correct |
3 |
Correct |
9 ms |
436 KB |
Output is correct |
4 |
Correct |
10 ms |
332 KB |
Output is correct |
5 |
Correct |
6 ms |
428 KB |
Output is correct |
6 |
Correct |
6 ms |
332 KB |
Output is correct |
7 |
Correct |
6 ms |
332 KB |
Output is correct |
8 |
Correct |
6 ms |
332 KB |
Output is correct |
9 |
Correct |
6 ms |
332 KB |
Output is correct |
10 |
Correct |
7 ms |
332 KB |
Output is correct |
11 |
Correct |
147 ms |
3252 KB |
Output is correct |
12 |
Correct |
123 ms |
3252 KB |
Output is correct |
13 |
Correct |
123 ms |
3324 KB |
Output is correct |
14 |
Correct |
115 ms |
3304 KB |
Output is correct |
15 |
Correct |
112 ms |
3320 KB |
Output is correct |
16 |
Correct |
128 ms |
3252 KB |
Output is correct |
17 |
Correct |
115 ms |
3300 KB |
Output is correct |
18 |
Correct |
125 ms |
3320 KB |
Output is correct |
19 |
Correct |
113 ms |
3252 KB |
Output is correct |
20 |
Correct |
118 ms |
3324 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
332 KB |
Output is correct |
2 |
Correct |
6 ms |
332 KB |
Output is correct |
3 |
Correct |
9 ms |
436 KB |
Output is correct |
4 |
Correct |
10 ms |
332 KB |
Output is correct |
5 |
Correct |
6 ms |
428 KB |
Output is correct |
6 |
Correct |
6 ms |
332 KB |
Output is correct |
7 |
Correct |
6 ms |
332 KB |
Output is correct |
8 |
Correct |
6 ms |
332 KB |
Output is correct |
9 |
Correct |
6 ms |
332 KB |
Output is correct |
10 |
Correct |
7 ms |
332 KB |
Output is correct |
11 |
Correct |
147 ms |
3252 KB |
Output is correct |
12 |
Correct |
123 ms |
3252 KB |
Output is correct |
13 |
Correct |
123 ms |
3324 KB |
Output is correct |
14 |
Correct |
115 ms |
3304 KB |
Output is correct |
15 |
Correct |
112 ms |
3320 KB |
Output is correct |
16 |
Correct |
128 ms |
3252 KB |
Output is correct |
17 |
Correct |
115 ms |
3300 KB |
Output is correct |
18 |
Correct |
125 ms |
3320 KB |
Output is correct |
19 |
Correct |
113 ms |
3252 KB |
Output is correct |
20 |
Correct |
118 ms |
3324 KB |
Output is correct |
21 |
Correct |
639 ms |
11248 KB |
Output is correct |
22 |
Correct |
623 ms |
11252 KB |
Output is correct |
23 |
Correct |
618 ms |
11248 KB |
Output is correct |
24 |
Correct |
649 ms |
11244 KB |
Output is correct |
25 |
Correct |
595 ms |
11244 KB |
Output is correct |
26 |
Correct |
588 ms |
11288 KB |
Output is correct |
27 |
Correct |
599 ms |
11184 KB |
Output is correct |
28 |
Correct |
595 ms |
11404 KB |
Output is correct |
29 |
Correct |
611 ms |
11252 KB |
Output is correct |
30 |
Correct |
603 ms |
11180 KB |
Output is correct |