oj.uz

Submission #405395

# Submission time Handle Problem Language Result Execution time Memory
405395 2021-05-16T10:40:53 Z Sundavar Index (COCI21_index) C++14
110 / 110
 995 ms 133476 KB 
#include <bits/stdc++.h>

using namespace std;

struct node{
    node* l = NULL,* r = NULL;
    int sum;
    node(node* l, node* r) : l(l), r(r){
        sum = (l ? l->sum : 0) + (r ? r->sum : 0);
    }
    node(int x) : sum(x){}
};
typedef node* pnode;
struct segTree{
    vector<pnode> root;
    int maxN;
    segTree(int n) : maxN(n){
        root.push_back(build(0, n));
    }
    pnode build(int l, int r){
        if(l == r-1) return new node(0);
        return new node(build(l, (l+r)/2), build((l+r)/2, r));
    }
    pnode update(pnode t, int poz, int c, int l, int r){
        if(l == r-1) return new node(t->sum + c);
        int m = (l+r)/2;
        if(poz < m) return new node(update(t->l, poz, c, l, m), t->r);
        return new node(t->l, update(t->r, poz, c, m, r));
    }
    void update(int poz, int c){
        root.push_back(update(root[root.size()-1], poz, c, 0, maxN));
    }
    int ask(pnode tl, pnode tr, int ex, int l, int r){
        if(l == r-1) return l;
        int m = (l+r)/2, sum = tr->r->sum - tl->r->sum;
        if(m <= sum+ex) return ask(tl->r, tr->r, ex, m, r);
        return ask(tl->l, tr->l, ex + sum, l, m);
    }
    int ask(int l, int r){
        return ask(root[l-1], root[r], 0, 0, maxN);
    }
};

int main(){
    cin.sync_with_stdio(false);
    cout.sync_with_stdio(false);
    int n,m;
    cin>>n>>m;
    vector<int> v(n);
    segTree tree = segTree(n);
    for(int i = 0; i < n; i++)
        cin>>v[i], tree.update(v[i], 1);
    while(m--){
        int l, r;
        cin>>l>>r;
        cout<<tree.ask(l, r)<<"\n";
    }
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 716 KB Output is correct
2 Correct 3 ms 716 KB Output is correct
3 Correct 4 ms 716 KB Output is correct
4 Correct 3 ms 716 KB Output is correct
5 Correct 5 ms 716 KB Output is correct
6 Correct 3 ms 716 KB Output is correct
7 Correct 3 ms 716 KB Output is correct
8 Correct 5 ms 716 KB Output is correct
9 Correct 3 ms 716 KB Output is correct
10 Correct 3 ms 716 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 716 KB Output is correct
2 Correct 3 ms 716 KB Output is correct
3 Correct 4 ms 716 KB Output is correct
4 Correct 3 ms 716 KB Output is correct
5 Correct 5 ms 716 KB Output is correct
6 Correct 3 ms 716 KB Output is correct
7 Correct 3 ms 716 KB Output is correct
8 Correct 5 ms 716 KB Output is correct
9 Correct 3 ms 716 KB Output is correct
10 Correct 3 ms 716 KB Output is correct
11 Correct 195 ms 30636 KB Output is correct
12 Correct 196 ms 30452 KB Output is correct
13 Correct 197 ms 30368 KB Output is correct
14 Correct 203 ms 30380 KB Output is correct
15 Correct 190 ms 30520 KB Output is correct
16 Correct 196 ms 30344 KB Output is correct
17 Correct 191 ms 30440 KB Output is correct
18 Correct 184 ms 30340 KB Output is correct
19 Correct 199 ms 30420 KB Output is correct
20 Correct 202 ms 30408 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 716 KB Output is correct
2 Correct 3 ms 716 KB Output is correct
3 Correct 4 ms 716 KB Output is correct
4 Correct 3 ms 716 KB Output is correct
5 Correct 5 ms 716 KB Output is correct
6 Correct 3 ms 716 KB Output is correct
7 Correct 3 ms 716 KB Output is correct
8 Correct 5 ms 716 KB Output is correct
9 Correct 3 ms 716 KB Output is correct
10 Correct 3 ms 716 KB Output is correct
11 Correct 195 ms 30636 KB Output is correct
12 Correct 196 ms 30452 KB Output is correct
13 Correct 197 ms 30368 KB Output is correct
14 Correct 203 ms 30380 KB Output is correct
15 Correct 190 ms 30520 KB Output is correct
16 Correct 196 ms 30344 KB Output is correct
17 Correct 191 ms 30440 KB Output is correct
18 Correct 184 ms 30340 KB Output is correct
19 Correct 199 ms 30420 KB Output is correct
20 Correct 202 ms 30408 KB Output is correct
21 Correct 968 ms 133428 KB Output is correct
22 Correct 995 ms 133384 KB Output is correct
23 Correct 976 ms 133388 KB Output is correct
24 Correct 985 ms 133356 KB Output is correct
25 Correct 932 ms 133388 KB Output is correct
26 Correct 958 ms 133428 KB Output is correct
27 Correct 968 ms 133476 KB Output is correct
28 Correct 949 ms 133432 KB Output is correct
29 Correct 972 ms 133460 KB Output is correct
30 Correct 959 ms 133432 KB Output is correct