#include <bits/stdc++.h>
using namespace std;
using ld = long double;
using ll = long long;
#define int ll
#define sz(x) (int)x.size()
const int N = 2e5+5;
int n, q;
int p[N];
vector<int> T[4*N];
void init(int i, int tl, int tr){
if(tl == tr){
T[i].push_back(p[tl]);
return;
}
int m = (tl + tr) / 2;
init(2*i+1, tl, m);
init(2*i+2, m+1, tr);
merge(T[2*i+1].begin(), T[2*i+1].end(), T[2*i+2].begin(), T[2*i+2].end(), back_inserter(T[i]));
}
int query(int l, int r, int k, int i, int tl, int tr){
if(r < tl or l > tr){
return 0;
}
if(l <= tl && tr <= r){
return lower_bound(T[i].begin(), T[i].end(), k) - T[i].begin();
}
int m = (tl + tr) / 2;
return query(l, r, k, 2*i+1, tl, m) + query(l, r, k, 2*i+2, m+1, tr);
}
int query(int l, int r, int k){
return query(l, r, k, 0, 0, n-1);
}
signed main(){
cin >> n >> q;
for(int i=0; i<n; ++i){
cin >> p[i];
}
init(0, 0, n-1);
while(q--){
int l, r;
cin >> l >> r;
l--, r--;
int low = 1, high = r - l + 1;
int res = 1;
while(low <= high){
int mid = (low + high) / 2;
int tmp = r - l + 1 - query(l, r, mid);
if(tmp >= mid){
res = mid;
low = mid+1;
} else {
high = mid-1;
}
}
cout << res << endl;
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
19292 KB |
Output is correct |
2 |
Correct |
10 ms |
19292 KB |
Output is correct |
3 |
Correct |
9 ms |
19288 KB |
Output is correct |
4 |
Correct |
15 ms |
19288 KB |
Output is correct |
5 |
Correct |
9 ms |
19292 KB |
Output is correct |
6 |
Correct |
9 ms |
19356 KB |
Output is correct |
7 |
Correct |
9 ms |
19292 KB |
Output is correct |
8 |
Correct |
10 ms |
19292 KB |
Output is correct |
9 |
Correct |
8 ms |
19292 KB |
Output is correct |
10 |
Correct |
10 ms |
19292 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
19292 KB |
Output is correct |
2 |
Correct |
10 ms |
19292 KB |
Output is correct |
3 |
Correct |
9 ms |
19288 KB |
Output is correct |
4 |
Correct |
15 ms |
19288 KB |
Output is correct |
5 |
Correct |
9 ms |
19292 KB |
Output is correct |
6 |
Correct |
9 ms |
19356 KB |
Output is correct |
7 |
Correct |
9 ms |
19292 KB |
Output is correct |
8 |
Correct |
10 ms |
19292 KB |
Output is correct |
9 |
Correct |
8 ms |
19292 KB |
Output is correct |
10 |
Correct |
10 ms |
19292 KB |
Output is correct |
11 |
Correct |
665 ms |
30220 KB |
Output is correct |
12 |
Correct |
659 ms |
30924 KB |
Output is correct |
13 |
Correct |
661 ms |
30988 KB |
Output is correct |
14 |
Correct |
659 ms |
30548 KB |
Output is correct |
15 |
Correct |
655 ms |
30700 KB |
Output is correct |
16 |
Correct |
660 ms |
30704 KB |
Output is correct |
17 |
Correct |
658 ms |
30984 KB |
Output is correct |
18 |
Correct |
667 ms |
31092 KB |
Output is correct |
19 |
Correct |
686 ms |
31188 KB |
Output is correct |
20 |
Correct |
648 ms |
30668 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
19292 KB |
Output is correct |
2 |
Correct |
10 ms |
19292 KB |
Output is correct |
3 |
Correct |
9 ms |
19288 KB |
Output is correct |
4 |
Correct |
15 ms |
19288 KB |
Output is correct |
5 |
Correct |
9 ms |
19292 KB |
Output is correct |
6 |
Correct |
9 ms |
19356 KB |
Output is correct |
7 |
Correct |
9 ms |
19292 KB |
Output is correct |
8 |
Correct |
10 ms |
19292 KB |
Output is correct |
9 |
Correct |
8 ms |
19292 KB |
Output is correct |
10 |
Correct |
10 ms |
19292 KB |
Output is correct |
11 |
Correct |
665 ms |
30220 KB |
Output is correct |
12 |
Correct |
659 ms |
30924 KB |
Output is correct |
13 |
Correct |
661 ms |
30988 KB |
Output is correct |
14 |
Correct |
659 ms |
30548 KB |
Output is correct |
15 |
Correct |
655 ms |
30700 KB |
Output is correct |
16 |
Correct |
660 ms |
30704 KB |
Output is correct |
17 |
Correct |
658 ms |
30984 KB |
Output is correct |
18 |
Correct |
667 ms |
31092 KB |
Output is correct |
19 |
Correct |
686 ms |
31188 KB |
Output is correct |
20 |
Correct |
648 ms |
30668 KB |
Output is correct |
21 |
Execution timed out |
2536 ms |
68104 KB |
Time limit exceeded |
22 |
Halted |
0 ms |
0 KB |
- |