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;
#define speed ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define rall(x) x.rbegin(), x.rend()
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define nl '\n'
//#define int long long
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double ld;
const int N = 2e5 + 5;
const int M = 1e3 + 5;
const int inf = 1e9 + 123;
const ll infl = 1e15 + 10;
const int mod = 1e9 + 7;
const int P = 31;
int n, q, MX, a[N], t[N], ans[N];
struct query{
int l, r, id;
};
vector <query> qs;
int sum (int r) {
int res = 0;
for (; r > 0; r -= r & -r)
res += t[r];
return res;
}
int sum (int l, int r) {
return sum(r) - sum(l-1);
}
void add (int k, int x) {
for (; k <= n; k += k & -k)
t[k] += x;
}
void add(int x){
add(x, 1);
}
void del(int x){
add(x, -1);
}
void solve() {
cin >> n >> q;
for(int i = 1; i <= n; i++)
cin >> a[i];
for(int i = 1; i <= q; i++){
int l, r;
cin >> l >> r;
qs.pb({l, r, i});
MX = max(MX, r);
}
sort(all(qs), [](query a, query b){
return a.r < b.r;
});
int l = 1, r = 0;
for(auto Q : qs){
while (r < Q.r)
add(a[++r]);
while (l < Q.l)
del(a[l++]);
while (l > Q.l)
add(a[--l]);
int l = 1, r = n + 1, mid;
while(r - l > 1){
mid = (l + r) >> 1;
if(sum(mid, MX) >= mid)
l = mid;
else
r = mid;
}
ans[Q.id] = l;
}
for(int i = 1; i <= q; i++)
cout << ans[i] << nl;
}
signed main() {
speed;
int T = 1;
// cin >> T;
while (T--)
solve();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |