This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/* chumeodiia */
/* TRY HARD */
#include<bits/stdc++.h>
#define MASK(x) (1LL << (x))
#define BIT(mask, i) (mask & (1LL << (i)))
// #define int long long
#define mp(x, y) make_pair(x, y)
using namespace std;
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
const int inf = 1e9 + 7;
const int S = 317;
const long long infll = 1e18 + 7;
typedef pair<int, int> pii;
int n, q, nNode;
int a[N], ver[N];
struct Node {
int left;
int right;
int sum;
} seg[10 * N];
int update(int oldId, int l, int r, int p, int v) {
if (l == r) {
a[l] += v;
++nNode;
seg[nNode].sum = a[l];
seg[nNode].left = seg[nNode].right = 0;
return nNode;
}
int mid = (l + r) / 2;
int cur = ++nNode;
if (p <= mid) {
seg[cur].left = update(seg[oldId].left, l, mid, p, v);
seg[cur].right = seg[oldId].right;
seg[cur].sum = seg[seg[cur].left].sum + seg[seg[cur].right].sum;
}
else {
seg[cur].left = seg[oldId].left;
seg[cur].right = update(seg[oldId].right, mid + 1, r, p, v);
seg[cur].sum = seg[seg[cur].left].sum + seg[seg[cur].right].sum;
}
return cur;
}
int get(int id, int l, int r, int u, int v) {
if (r < u || l > v) return 0;
if (l >= u && r <= v) return seg[id].sum;
int mid = (l + r) / 2;
return get(seg[id].left, l, mid, u, v) + get(seg[id].right, mid + 1, r, u, v);
}
signed main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> q;
for (int i = 1; i <= n; i++) {
int x; cin >> x;
ver[i] = update(ver[i - 1], 1, N - 1, x, 1);
}
while (q--) {
int l, r; cin >> l >> r;
int lo = 1, hi = N - 1;
int ans = 1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (get(ver[r], 1, N - 1, mid, N - 1) - get(ver[l - 1], 1, N - 1, mid, N - 1) >= mid) {
ans = mid;
lo = mid + 1;
} else hi = mid - 1;
}
cout << ans << '\n';
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |