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;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef pair<int, int> pii;
//mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#define pb push_back
#define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define TC int __TC__; cin >> __TC__; while(__TC__--)
#define ar array
const int INF = 1e9 + 7, N = 2e5;
int n, q, p[N];
struct node{
node* left = nullptr,* right = nullptr;
int v = 0;
};
node* root[N+1];
void build(node *rt, int lx, int rx){
if(lx == rx) return;
int m = lx+(rx-lx) / 2;
rt->left = new node;
rt->right = new node;
build(rt->left, lx, m);
build(rt->right, m+1, rx);
return;
}
void add(int pos, node* lr, node* nr, int lx, int rx){
if(lx == rx){
++nr->v;
return;
}
int m = lx + (rx - lx) / 2;
if(pos <= m){ // go left
nr->right = lr->right;
nr->left = new node;
nr->left->v = lr->left->v;
add(pos, lr->left, nr->left, lx, m);
}else{ // go right
nr->left = lr->left;
nr->right = new node;
nr->right->v = lr->right->v;
add(pos, lr->right, nr->right, m+1, rx);
}
nr->v = nr->left->v + nr->right->v;
}
int get(int l, int r, node* rt, int lx, int rx){
if(r < lx || l > rx) return 0;
if(lx >= l && rx <= r) return rt->v;
int m = lx + (rx - lx) / 2;
return get(l, r, rt->left, lx, m) + get(l, r, rt->right, m+1, rx);
}
int main(void)
{
FAST;
cin >> n >> q;
for(int i = 0; i < n; ++i){
cin >> p[i];
}
root[0] = new node;
build(root[0], 1, N);
for(int i = 1; i <= n; ++i){
root[i] = new node;
add(p[i-1], root[i-1], root[i], 1, N);
}
while(q--){
int l, r; cin >> l >> r;
int ans = 0;
for(int j = 18; j >= 0; --j){
int nans = ans + (1<<j);
if(nans > N) continue;
if(get(nans, N, root[r], 1, N) - get(nans, N, root[l-1], 1, N) >= nans) ans += (1<<j);
}
cout << ans << '\n';
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |