oj.uz

Submission #857349

# Submission time Handle Problem Language Result Execution time Memory
857349 2023-10-06T01:36:04 Z 12345678 Index (COCI21_index) C++17
110 / 110
 392 ms 136740 KB 
#include <bits/stdc++.h>

using namespace std;

const int nx=2e5+5;
int n, q, p, l, r;

struct persist
{
    struct node
    {
        int d;
        node *l, *r;
        node(): d(0), l(0), r(0){}
    };
    typedef node* pnode;
    pnode rt[nx];
    void build(int l, int r, pnode &t)
    {
        t=new node();
        if (l==r) return;
        int md=(l+r)/2;
        build(l, md, t->l);
        build(md+1, r, t->r);
    }
    void update(int l, int r, pnode &t, pnode k, int idx)
    {
        t=new node(*k);
        if (l==r) return t->d=k->d+1, void();
        int md=(l+r)/2;
        if (idx<=md) update(l, md, t->l, k->l, idx);
        else update(md+1, r, t->r, k->r, idx);
        t->d=t->l->d+t->r->d;
    }
    int query(int l, int r, pnode pl, pnode pr, int sv)
    {
        //printf("%d %d %d\n", l, r, pr->d-pl->d);
        if (l==r) return l;
        int md=(l+r)/2;
        if (pr->r->d-pl->r->d+sv>=md+1) return query(md+1, r, pl->r, pr->r, sv);
        else return query(l, md, pl->l, pr->l, pr->r->d-pl->r->d+sv);
    }
} s;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>q;
    s.build(1, nx-1, s.rt[0]);
    for (int i=1; i<=n; i++) cin>>p, s.update(1, nx-1, s.rt[i], s.rt[i-1], p);
    while (q--)
    {
        cin>>l>>r;
        cout<<s.query(1, nx-1, s.rt[l-1], s.rt[r], 0)<<'\n';
    }
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 13392 KB Output is correct
2 Correct 12 ms 13404 KB Output is correct
3 Correct 12 ms 13404 KB Output is correct
4 Correct 12 ms 13476 KB Output is correct
5 Correct 14 ms 13400 KB Output is correct
6 Correct 16 ms 13404 KB Output is correct
7 Correct 12 ms 13404 KB Output is correct
8 Correct 13 ms 13404 KB Output is correct
9 Correct 12 ms 13408 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 15 ms 13392 KB Output is correct
2 Correct 12 ms 13404 KB Output is correct
3 Correct 12 ms 13404 KB Output is correct
4 Correct 12 ms 13476 KB Output is correct
5 Correct 14 ms 13400 KB Output is correct
6 Correct 16 ms 13404 KB Output is correct
7 Correct 12 ms 13404 KB Output is correct
8 Correct 13 ms 13404 KB Output is correct
9 Correct 12 ms 13408 KB Output is correct
10 Correct 12 ms 13404 KB Output is correct
11 Correct 79 ms 43844 KB Output is correct
12 Correct 70 ms 43600 KB Output is correct
13 Correct 79 ms 43604 KB Output is correct
14 Correct 69 ms 43620 KB Output is correct
15 Correct 70 ms 43568 KB Output is correct
16 Correct 77 ms 43648 KB Output is correct
17 Correct 86 ms 43584 KB Output is correct
18 Correct 73 ms 43728 KB Output is correct
19 Correct 70 ms 43592 KB Output is correct
20 Correct 80 ms 43684 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 13392 KB Output is correct
2 Correct 12 ms 13404 KB Output is correct
3 Correct 12 ms 13404 KB Output is correct
4 Correct 12 ms 13476 KB Output is correct
5 Correct 14 ms 13400 KB Output is correct
6 Correct 16 ms 13404 KB Output is correct
7 Correct 12 ms 13404 KB Output is correct
8 Correct 13 ms 13404 KB Output is correct
9 Correct 12 ms 13408 KB Output is correct
10 Correct 12 ms 13404 KB Output is correct
11 Correct 79 ms 43844 KB Output is correct
12 Correct 70 ms 43600 KB Output is correct
13 Correct 79 ms 43604 KB Output is correct
14 Correct 69 ms 43620 KB Output is correct
15 Correct 70 ms 43568 KB Output is correct
16 Correct 77 ms 43648 KB Output is correct
17 Correct 86 ms 43584 KB Output is correct
18 Correct 73 ms 43728 KB Output is correct
19 Correct 70 ms 43592 KB Output is correct
20 Correct 80 ms 43684 KB Output is correct
21 Correct 341 ms 136448 KB Output is correct
22 Correct 349 ms 136488 KB Output is correct
23 Correct 342 ms 136404 KB Output is correct
24 Correct 342 ms 136740 KB Output is correct
25 Correct 392 ms 136396 KB Output is correct
26 Correct 346 ms 136292 KB Output is correct
27 Correct 344 ms 136272 KB Output is correct
28 Correct 368 ms 136248 KB Output is correct
29 Correct 342 ms 136344 KB Output is correct
30 Correct 371 ms 136424 KB Output is correct