#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
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);
| ~~~~~^~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
972 KB |
Output is correct |
2 |
Correct |
4 ms |
972 KB |
Output is correct |
3 |
Correct |
5 ms |
972 KB |
Output is correct |
4 |
Correct |
4 ms |
972 KB |
Output is correct |
5 |
Correct |
4 ms |
972 KB |
Output is correct |
6 |
Correct |
5 ms |
972 KB |
Output is correct |
7 |
Correct |
4 ms |
972 KB |
Output is correct |
8 |
Correct |
4 ms |
972 KB |
Output is correct |
9 |
Correct |
4 ms |
972 KB |
Output is correct |
10 |
Correct |
4 ms |
1028 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
972 KB |
Output is correct |
2 |
Correct |
4 ms |
972 KB |
Output is correct |
3 |
Correct |
5 ms |
972 KB |
Output is correct |
4 |
Correct |
4 ms |
972 KB |
Output is correct |
5 |
Correct |
4 ms |
972 KB |
Output is correct |
6 |
Correct |
5 ms |
972 KB |
Output is correct |
7 |
Correct |
4 ms |
972 KB |
Output is correct |
8 |
Correct |
4 ms |
972 KB |
Output is correct |
9 |
Correct |
4 ms |
972 KB |
Output is correct |
10 |
Correct |
4 ms |
1028 KB |
Output is correct |
11 |
Correct |
283 ms |
37188 KB |
Output is correct |
12 |
Correct |
265 ms |
37060 KB |
Output is correct |
13 |
Correct |
271 ms |
37136 KB |
Output is correct |
14 |
Correct |
280 ms |
37168 KB |
Output is correct |
15 |
Correct |
269 ms |
37136 KB |
Output is correct |
16 |
Correct |
273 ms |
37292 KB |
Output is correct |
17 |
Correct |
274 ms |
37136 KB |
Output is correct |
18 |
Correct |
295 ms |
37188 KB |
Output is correct |
19 |
Correct |
280 ms |
37120 KB |
Output is correct |
20 |
Correct |
272 ms |
37152 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
972 KB |
Output is correct |
2 |
Correct |
4 ms |
972 KB |
Output is correct |
3 |
Correct |
5 ms |
972 KB |
Output is correct |
4 |
Correct |
4 ms |
972 KB |
Output is correct |
5 |
Correct |
4 ms |
972 KB |
Output is correct |
6 |
Correct |
5 ms |
972 KB |
Output is correct |
7 |
Correct |
4 ms |
972 KB |
Output is correct |
8 |
Correct |
4 ms |
972 KB |
Output is correct |
9 |
Correct |
4 ms |
972 KB |
Output is correct |
10 |
Correct |
4 ms |
1028 KB |
Output is correct |
11 |
Correct |
283 ms |
37188 KB |
Output is correct |
12 |
Correct |
265 ms |
37060 KB |
Output is correct |
13 |
Correct |
271 ms |
37136 KB |
Output is correct |
14 |
Correct |
280 ms |
37168 KB |
Output is correct |
15 |
Correct |
269 ms |
37136 KB |
Output is correct |
16 |
Correct |
273 ms |
37292 KB |
Output is correct |
17 |
Correct |
274 ms |
37136 KB |
Output is correct |
18 |
Correct |
295 ms |
37188 KB |
Output is correct |
19 |
Correct |
280 ms |
37120 KB |
Output is correct |
20 |
Correct |
272 ms |
37152 KB |
Output is correct |
21 |
Correct |
1665 ms |
147960 KB |
Output is correct |
22 |
Correct |
1620 ms |
151600 KB |
Output is correct |
23 |
Correct |
1589 ms |
151472 KB |
Output is correct |
24 |
Correct |
1624 ms |
151664 KB |
Output is correct |
25 |
Correct |
1614 ms |
151596 KB |
Output is correct |
26 |
Correct |
1622 ms |
151688 KB |
Output is correct |
27 |
Correct |
1641 ms |
151840 KB |
Output is correct |
28 |
Correct |
1658 ms |
151688 KB |
Output is correct |
29 |
Correct |
1621 ms |
151572 KB |
Output is correct |
30 |
Correct |
1665 ms |
151672 KB |
Output is correct |