This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
constexpr int sz = 1001;
int n, Q, c[sz], ans[sz];
int j, tree[sz][sz];
inline void update(int pos, int val){
while(pos <= n){
tree[j][pos] += val;
pos += (pos & (-pos));
}
return;
}
int get_ans(int l, int r){
if(!r || l > r) return 0;
if(l ^ 1) return get_ans(1, r) - get_ans(1, l - 1);
int res(0);
while(r > 0){
res += tree[j][r];
r -= (r & (-r));
}
return res;
}
struct que{
int index, l, r;
} q[sz];
bool cmp(que a, que b){
if(a.r ^ b.r) return a.r < b.r;
return a.l < b.l;
}
bool check(int mid, int l, int r){
int cur(0);
j = r;
cur += get_ans(mid, n);
j = l - 1;
if(j > 0) cur -= get_ans(mid, n);
return cur >= mid;
}
signed main(){
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> Q;
for(register int i = 1; i <= n; ++i){
cin >> c[i];
for(j = i; j <= n; ++j){
update(c[i], 1);
}
}
for(register int i = 1; i <= Q; ++i){
cin >> q[i].l >> q[i].r, q[i].index = i;
}
sort(q+1, q+Q+1, cmp);
int i(1), l, r;
while(i <= n){
l = q[i].l, r = q[i].r;
int L(1), R(r - l + 1), mid, best(1);
while(L <= R){
mid = L + ((R - L) >> 1);
if(check(mid, l, r)){
best = mid;
L = mid + 1;
}else{
R = mid - 1;
}
}
ans[q[i].index] = best;
++i;
}
for(register int i = 1; i <= Q; ++i){
cout << ans[i] << '\n';
}
return 0;
}
/*
7 6
3 2 3 1 1 4 7
3 4
1 7
1 6
4 5
1 2
5 7
*/
Compilation message (stderr)
index.cpp: In function 'int main()':
index.cpp:56:19: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
56 | for(register int i = 1; i <= n; ++i){
| ^
index.cpp:62:19: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
62 | for(register int i = 1; i <= Q; ++i){
| ^
index.cpp:91:19: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
91 | for(register int i = 1; i <= Q; ++i){
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |