# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
440146 |
2021-07-01T16:16:32 Z |
FatihSolak |
Index (COCI21_index) |
C++17 |
|
2380 ms |
134304 KB |
#include <bits/stdc++.h>
#define N 200005
using namespace std;
int arr[N];
int cnt[N];
struct Node{
int sum;
Node *lc,*rc;
Node(int a){
sum = a;
}
Node(Node *a, Node *b){
sum = a->sum + b->sum;
lc = a;
rc = b;
}
};
Node* build(int l,int r){
if(l == r){
return new Node(cnt[l]);
}
int m = (l+r)/2;
return new Node(build(l,m),build(m+1,r));
}
Node* upd(Node* v,int l,int r,int pos,int val){
if(l == r){
return new Node(v->sum + val);
}
int m = (l+r)/2;
if(pos <=m){
return new Node(upd(v->lc,l,m,pos,val),v->rc);
}
else return new Node(v->lc,upd(v->rc,m+1,r,pos,val));
}
int mt;
int get(Node* v1,Node* v2,int tl,int tr, int l){
if(tr < l){
return 0;
}
if(l <= tl){
return v1->sum - v2 -> sum;
}
mt = (tl+tr)/2;
return get(v1->lc,v2->lc,tl,mt,l) + get(v1->rc,v2->rc,mt+1,tr,l);
}
int get(Node* v,int tl,int tr, int l){
if(tr < l){
return 0;
}
if(l <= tl){
return v->sum;
}
mt = (tl+tr)/2;
return get(v->lc,tl,mt,l) + get(v->rc,mt+1,tr,l);
}
Node* roots[N];
int main(){
int n,q;
scanf("%d%d",&n,&q);
for(int i=0;i<n;i++){
scanf("%d",&arr[i]);
cnt[arr[i]]++;
}
roots[0] = build(1,N-1);
for(int i=1;i<n;i++){
roots[i] = upd(roots[i-1],1,N-1,arr[i-1],-1);
}
int ql,qr;
int l,r,m,val;
while(q--){
scanf("%d%d",&ql,&qr);
ql--,qr--;
l = 1,r = qr-ql+1;
while(l < r){
m = (l+r+1)/2;
if(qr +1 != n){
val = get(roots[ql],roots[qr+1],1,N-1,m);
}
else val = get(roots[ql],1,N-1,m);
if(val >= m){
l = m;
}
else r = m-1;
}
printf("%d\n",l);
}
}
Compilation message
index.cpp: In function 'int main()':
index.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
59 | scanf("%d%d",&n,&q);
| ~~~~~^~~~~~~~~~~~~~
index.cpp:61:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
61 | scanf("%d",&arr[i]);
| ~~~~~^~~~~~~~~~~~~~
index.cpp:71:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
71 | scanf("%d%d",&ql,&qr);
| ~~~~~^~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
13388 KB |
Output is correct |
2 |
Correct |
20 ms |
13432 KB |
Output is correct |
3 |
Correct |
21 ms |
13404 KB |
Output is correct |
4 |
Correct |
21 ms |
13428 KB |
Output is correct |
5 |
Correct |
21 ms |
13388 KB |
Output is correct |
6 |
Correct |
20 ms |
13388 KB |
Output is correct |
7 |
Correct |
20 ms |
13384 KB |
Output is correct |
8 |
Correct |
21 ms |
13416 KB |
Output is correct |
9 |
Correct |
20 ms |
13388 KB |
Output is correct |
10 |
Correct |
20 ms |
13328 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
13388 KB |
Output is correct |
2 |
Correct |
20 ms |
13432 KB |
Output is correct |
3 |
Correct |
21 ms |
13404 KB |
Output is correct |
4 |
Correct |
21 ms |
13428 KB |
Output is correct |
5 |
Correct |
21 ms |
13388 KB |
Output is correct |
6 |
Correct |
20 ms |
13388 KB |
Output is correct |
7 |
Correct |
20 ms |
13384 KB |
Output is correct |
8 |
Correct |
21 ms |
13416 KB |
Output is correct |
9 |
Correct |
20 ms |
13388 KB |
Output is correct |
10 |
Correct |
20 ms |
13328 KB |
Output is correct |
11 |
Correct |
336 ms |
43304 KB |
Output is correct |
12 |
Correct |
318 ms |
43256 KB |
Output is correct |
13 |
Correct |
364 ms |
43236 KB |
Output is correct |
14 |
Correct |
311 ms |
43144 KB |
Output is correct |
15 |
Correct |
332 ms |
43072 KB |
Output is correct |
16 |
Correct |
435 ms |
43100 KB |
Output is correct |
17 |
Correct |
331 ms |
43144 KB |
Output is correct |
18 |
Correct |
340 ms |
43204 KB |
Output is correct |
19 |
Correct |
319 ms |
43092 KB |
Output is correct |
20 |
Correct |
351 ms |
43080 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
13388 KB |
Output is correct |
2 |
Correct |
20 ms |
13432 KB |
Output is correct |
3 |
Correct |
21 ms |
13404 KB |
Output is correct |
4 |
Correct |
21 ms |
13428 KB |
Output is correct |
5 |
Correct |
21 ms |
13388 KB |
Output is correct |
6 |
Correct |
20 ms |
13388 KB |
Output is correct |
7 |
Correct |
20 ms |
13384 KB |
Output is correct |
8 |
Correct |
21 ms |
13416 KB |
Output is correct |
9 |
Correct |
20 ms |
13388 KB |
Output is correct |
10 |
Correct |
20 ms |
13328 KB |
Output is correct |
11 |
Correct |
336 ms |
43304 KB |
Output is correct |
12 |
Correct |
318 ms |
43256 KB |
Output is correct |
13 |
Correct |
364 ms |
43236 KB |
Output is correct |
14 |
Correct |
311 ms |
43144 KB |
Output is correct |
15 |
Correct |
332 ms |
43072 KB |
Output is correct |
16 |
Correct |
435 ms |
43100 KB |
Output is correct |
17 |
Correct |
331 ms |
43144 KB |
Output is correct |
18 |
Correct |
340 ms |
43204 KB |
Output is correct |
19 |
Correct |
319 ms |
43092 KB |
Output is correct |
20 |
Correct |
351 ms |
43080 KB |
Output is correct |
21 |
Correct |
2314 ms |
134056 KB |
Output is correct |
22 |
Correct |
2338 ms |
134096 KB |
Output is correct |
23 |
Correct |
2283 ms |
134280 KB |
Output is correct |
24 |
Correct |
2380 ms |
134076 KB |
Output is correct |
25 |
Correct |
2302 ms |
134116 KB |
Output is correct |
26 |
Correct |
2163 ms |
134060 KB |
Output is correct |
27 |
Correct |
2320 ms |
134144 KB |
Output is correct |
28 |
Correct |
2263 ms |
134112 KB |
Output is correct |
29 |
Correct |
2371 ms |
134304 KB |
Output is correct |
30 |
Correct |
2238 ms |
134176 KB |
Output is correct |