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 double lf;
typedef long double Lf;
typedef pair <int,int> pii;
typedef pair <ll, ll> pll;
#define TRACE(x) cerr << #x << " " << x << endl
#define FOR(i, a, b) for (int i = (a); i < int(b); i++)
#define REP(i, n) FOR(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define _ << " " <<
#define fi first
#define sec second
#define mp make_pair
#define pb push_back
const int MAXN = 200001;
struct node {
int x;
node* l;
node* r;
node (int y = 0,node *L = 0, node *R = 0) {
x = y;
l = L;
r = R;
}
};
node* nil() {
node *x = new node();
x -> r = x -> l = x;
return x;
}
const int offset = (1 << 18);
int n, q, p[MAXN];
node* root[MAXN];
node* tmp;
vector <int> v;
node* update(node* cvor, int lo,int hi, int x) {
if (x < lo || x > hi) return cvor;
if (lo == hi && lo == x) return new node (cvor -> x + 1, nil(), nil());
node* left;
node* right;
int mid = (lo + hi) / 2;
left = update(cvor -> l, lo, mid, x);
right = update(cvor -> r, mid + 1, hi, x);
return new node (left -> x + right -> x, left, right);
}
int query(node *cvor, node* cvor1, int lo, int hi, int x) {
if (hi < x || lo >= MAXN) return 0;
if (lo >= x) return cvor -> x - cvor1 -> x;
int mid = (lo + hi) >> 1;
int ret = 0;
ret += query(cvor -> l, cvor1 -> l, lo, mid, x);
ret += query(cvor -> r, cvor1 -> r, mid + 1, hi, x);
return ret;
}
int main() {
scanf("%d %d",&n,&q);
for (int i = 0;i < n; i++) {
scanf("%d",&p[i]);
tmp = nil();
if (i) tmp = root[i - 1];
root[i] = update(tmp, 0, offset - 1, p[i]);
}
for (int i = 0; i < q; i++) {
int A, B;
scanf("%d %d",&A,&B);
A--; B--;
tmp = nil();
int lo = 0, hi = MAXN, mid;
while (lo != hi) {
mid = (lo + hi + 1) / 2;
if (A) tmp = root[A - 1];
int t = query(root[B], tmp, 0, offset - 1, mid);
if (t >= mid) lo = mid;
else hi = mid - 1;
}
printf("%d\n",lo);
}
return 0;
}
Compilation message (stderr)
index.cpp: In function 'int main()':
index.cpp:76:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
76 | scanf("%d %d",&n,&q);
| ~~~~~^~~~~~~~~~~~~~~
index.cpp:79:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
79 | scanf("%d",&p[i]);
| ~~~~~^~~~~~~~~~~~
index.cpp:87:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
87 | scanf("%d %d",&A,&B);
| ~~~~~^~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |