oj.uz

Submission #928999

# Submission time Handle Problem Language Result Execution time Memory
928999 2024-02-17T12:43:11 Z Warinchai Index (COCI21_index) C++14
110 / 110
 411 ms 136628 KB 
#include<bits/stdc++.h>
using namespace std;
int inf=1e9;
struct segtree{
    struct node{
        int sum;
        node *l,*r;
        node(int x=0){
            sum=x;
            l=r=NULL;
        }
    };
    typedef node* pnode;
    pnode rt[200005];
    int getsum(pnode x){
        return x?x->sum:0;
    }
    void upd(int st,int en,pnode x,pnode &y,int pos,int val){
        y=new node(*x);
        if(st==en){
            y->sum+=val;
            return void();
        }
        int m=(st+en)/2;
        if(pos<=m)upd(st,m,x->l,y->l,pos,val);
        else upd(m+1,en,x->r,y->r,pos,val);
        y->sum=getsum(y->l)+getsum(y->r);
    }
    int fans(int st,int en,pnode x,pnode y,int s=0){
        if(st==en)return st;
        int m=(st+en)/2;
        if(getsum(y->r)-getsum(x->r)+s>=m+1)return fans(m+1,en,x->r,y->r,s);
        else return fans(st,m,x->l,y->l,s+getsum(y->r)-getsum(x->r));
    }
    void build(int st,int en,pnode &x){
        x=new node();
        if(st==en)return;
        int m=(st+en)/2;
        build(st,m,x->l);
        build(m+1,en,x->r);
    }
}tr;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,q;cin>>n>>q;
    tr.build(1,2e5,tr.rt[0]);
    for(int i=1;i<=n;i++){
        int a;cin>>a;
        tr.upd(1,2e5,tr.rt[i-1],tr.rt[i],a,1);
    }
    for(int i=1;i<=q;i++){
        int l,r;cin>>l>>r;
        cout<<tr.fans(1,2e5,tr.rt[l-1],tr.rt[r])<<"\n";
    }
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 13400 KB Output is correct
2 Correct 12 ms 13444 KB Output is correct
3 Correct 17 ms 13404 KB Output is correct
4 Correct 14 ms 13512 KB Output is correct
5 Correct 12 ms 13404 KB Output is correct
6 Correct 12 ms 13404 KB Output is correct
7 Correct 14 ms 13656 KB Output is correct
8 Correct 12 ms 13404 KB Output is correct
9 Correct 12 ms 13492 KB Output is correct
10 Correct 12 ms 13404 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 13400 KB Output is correct
2 Correct 12 ms 13444 KB Output is correct
3 Correct 17 ms 13404 KB Output is correct
4 Correct 14 ms 13512 KB Output is correct
5 Correct 12 ms 13404 KB Output is correct
6 Correct 12 ms 13404 KB Output is correct
7 Correct 14 ms 13656 KB Output is correct
8 Correct 12 ms 13404 KB Output is correct
9 Correct 12 ms 13492 KB Output is correct
10 Correct 12 ms 13404 KB Output is correct
11 Correct 70 ms 43604 KB Output is correct
12 Correct 71 ms 43640 KB Output is correct
13 Correct 70 ms 43600 KB Output is correct
14 Correct 78 ms 43560 KB Output is correct
15 Correct 90 ms 43604 KB Output is correct
16 Correct 71 ms 43716 KB Output is correct
17 Correct 77 ms 43560 KB Output is correct
18 Correct 73 ms 43724 KB Output is correct
19 Correct 70 ms 43604 KB Output is correct
20 Correct 70 ms 43600 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 13400 KB Output is correct
2 Correct 12 ms 13444 KB Output is correct
3 Correct 17 ms 13404 KB Output is correct
4 Correct 14 ms 13512 KB Output is correct
5 Correct 12 ms 13404 KB Output is correct
6 Correct 12 ms 13404 KB Output is correct
7 Correct 14 ms 13656 KB Output is correct
8 Correct 12 ms 13404 KB Output is correct
9 Correct 12 ms 13492 KB Output is correct
10 Correct 12 ms 13404 KB Output is correct
11 Correct 70 ms 43604 KB Output is correct
12 Correct 71 ms 43640 KB Output is correct
13 Correct 70 ms 43600 KB Output is correct
14 Correct 78 ms 43560 KB Output is correct
15 Correct 90 ms 43604 KB Output is correct
16 Correct 71 ms 43716 KB Output is correct
17 Correct 77 ms 43560 KB Output is correct
18 Correct 73 ms 43724 KB Output is correct
19 Correct 70 ms 43604 KB Output is correct
20 Correct 70 ms 43600 KB Output is correct
21 Correct 352 ms 136276 KB Output is correct
22 Correct 364 ms 136356 KB Output is correct
23 Correct 377 ms 136364 KB Output is correct
24 Correct 365 ms 136396 KB Output is correct
25 Correct 355 ms 136628 KB Output is correct
26 Correct 353 ms 136268 KB Output is correct
27 Correct 354 ms 136528 KB Output is correct
28 Correct 373 ms 136408 KB Output is correct
29 Correct 380 ms 136220 KB Output is correct
30 Correct 411 ms 136448 KB Output is correct