oj.uz

Submission #405394

# Submission time Handle Problem Language Result Execution time Memory
405394 2021-05-16T10:38:40 Z Sundavar Index (COCI21_index) C++14
110 / 110
 1172 ms 137196 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(){
    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 4 ms 716 KB Output is correct
2 Correct 4 ms 716 KB Output is correct
3 Correct 4 ms 680 KB Output is correct
4 Correct 4 ms 680 KB Output is correct
5 Correct 4 ms 716 KB Output is correct
6 Correct 5 ms 680 KB Output is correct
7 Correct 5 ms 716 KB Output is correct
8 Correct 5 ms 716 KB Output is correct
9 Correct 4 ms 716 KB Output is correct
10 Correct 4 ms 716 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 716 KB Output is correct
2 Correct 4 ms 716 KB Output is correct
3 Correct 4 ms 680 KB Output is correct
4 Correct 4 ms 680 KB Output is correct
5 Correct 4 ms 716 KB Output is correct
6 Correct 5 ms 680 KB Output is correct
7 Correct 5 ms 716 KB Output is correct
8 Correct 5 ms 716 KB Output is correct
9 Correct 4 ms 716 KB Output is correct
10 Correct 4 ms 716 KB Output is correct
11 Correct 231 ms 31276 KB Output is correct
12 Correct 240 ms 31136 KB Output is correct
13 Correct 242 ms 31192 KB Output is correct
14 Correct 212 ms 31256 KB Output is correct
15 Correct 247 ms 31264 KB Output is correct
16 Correct 248 ms 31252 KB Output is correct
17 Correct 242 ms 31160 KB Output is correct
18 Correct 226 ms 31220 KB Output is correct
19 Correct 223 ms 31292 KB Output is correct
20 Correct 213 ms 31248 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 716 KB Output is correct
2 Correct 4 ms 716 KB Output is correct
3 Correct 4 ms 680 KB Output is correct
4 Correct 4 ms 680 KB Output is correct
5 Correct 4 ms 716 KB Output is correct
6 Correct 5 ms 680 KB Output is correct
7 Correct 5 ms 716 KB Output is correct
8 Correct 5 ms 716 KB Output is correct
9 Correct 4 ms 716 KB Output is correct
10 Correct 4 ms 716 KB Output is correct
11 Correct 231 ms 31276 KB Output is correct
12 Correct 240 ms 31136 KB Output is correct
13 Correct 242 ms 31192 KB Output is correct
14 Correct 212 ms 31256 KB Output is correct
15 Correct 247 ms 31264 KB Output is correct
16 Correct 248 ms 31252 KB Output is correct
17 Correct 242 ms 31160 KB Output is correct
18 Correct 226 ms 31220 KB Output is correct
19 Correct 223 ms 31292 KB Output is correct
20 Correct 213 ms 31248 KB Output is correct
21 Correct 1127 ms 137140 KB Output is correct
22 Correct 1092 ms 137196 KB Output is correct
23 Correct 1172 ms 137172 KB Output is correct
24 Correct 1090 ms 137140 KB Output is correct
25 Correct 1081 ms 137016 KB Output is correct
26 Correct 1121 ms 136988 KB Output is correct
27 Correct 1122 ms 137140 KB Output is correct
28 Correct 1092 ms 137096 KB Output is correct
29 Correct 1134 ms 137140 KB Output is correct
30 Correct 1167 ms 137100 KB Output is correct