oj.uz

Submission #1079464

# Submission time Handle Problem Language Result Execution time Memory
1079464 2024-08-28T15:07:56 Z 12345678 Index (COCI21_index) C++17
110 / 110
 370 ms 137236 KB 
#include <bits/stdc++.h>

using namespace std;

const int nx=2e5+5;

int n, q, p[nx], l, r;

struct persistsegtree
{
    struct node
    {
        int sm;
        node *l, *r;
        node(int sm): sm(sm), l(0), r(0){}
    };
    typedef node* pnode;
    pnode rt[nx];
    void build(int l, int r, pnode &k)
    {
        k=new node(0);
        if (l==r) return;
        int md=(l+r)/2;
        build(l, md, k->l);
        build(md+1, r, k->r);
    }
    void update(int l, int r, pnode &k, pnode t, int idx)
    {
        k=new node(*t);
        if (l==r) return k->sm++, void();
        int md=(l+r)/2;
        if (idx<=md) update(l, md, k->l, t->l, idx);
        else update(md+1, r, k->r, t->r, idx);
        k->sm=k->l->sm+k->r->sm;
    }
    int query(int l, int r, pnode k, pnode t, int sv)
    {
        if (l==r) return l;
        int md=(l+r)/2;
        if (k->r->sm-t->r->sm+sv>=md+1) return query(md+1, r, k->r, t->r, sv);
        else return query(l, md, k->l, t->l, sv+k->r->sm-t->r->sm);
    }
} s;

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

Subtask #1
20.0 / 20.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2908 KB Output is correct
2 Correct 1 ms 2908 KB Output is correct
3 Correct 1 ms 2944 KB Output is correct
4 Correct 1 ms 2908 KB Output is correct
5 Correct 1 ms 2908 KB Output is correct
6 Correct 1 ms 2908 KB Output is correct
7 Correct 1 ms 2908 KB Output is correct
8 Correct 1 ms 2908 KB Output is correct
9 Correct 1 ms 2908 KB Output is correct
10 Correct 1 ms 2712 KB Output is correct
11 Correct 64 ms 32912 KB Output is correct
12 Correct 70 ms 32988 KB Output is correct
13 Correct 63 ms 32948 KB Output is correct
14 Correct 60 ms 32852 KB Output is correct
15 Correct 62 ms 32960 KB Output is correct
16 Correct 58 ms 32852 KB Output is correct
17 Correct 70 ms 32916 KB Output is correct
18 Correct 63 ms 32848 KB Output is correct
19 Correct 61 ms 32852 KB Output is correct
20 Correct 61 ms 32968 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2908 KB Output is correct
2 Correct 1 ms 2908 KB Output is correct
3 Correct 1 ms 2944 KB Output is correct
4 Correct 1 ms 2908 KB Output is correct
5 Correct 1 ms 2908 KB Output is correct
6 Correct 1 ms 2908 KB Output is correct
7 Correct 1 ms 2908 KB Output is correct
8 Correct 1 ms 2908 KB Output is correct
9 Correct 1 ms 2908 KB Output is correct
10 Correct 1 ms 2712 KB Output is correct
11 Correct 64 ms 32912 KB Output is correct
12 Correct 70 ms 32988 KB Output is correct
13 Correct 63 ms 32948 KB Output is correct
14 Correct 60 ms 32852 KB Output is correct
15 Correct 62 ms 32960 KB Output is correct
16 Correct 58 ms 32852 KB Output is correct
17 Correct 70 ms 32916 KB Output is correct
18 Correct 63 ms 32848 KB Output is correct
19 Correct 61 ms 32852 KB Output is correct
20 Correct 61 ms 32968 KB Output is correct
21 Correct 346 ms 137012 KB Output is correct
22 Correct 339 ms 137012 KB Output is correct
23 Correct 334 ms 137204 KB Output is correct
24 Correct 331 ms 137044 KB Output is correct
25 Correct 370 ms 137236 KB Output is correct
26 Correct 313 ms 137044 KB Output is correct
27 Correct 337 ms 137112 KB Output is correct
28 Correct 333 ms 137044 KB Output is correct
29 Correct 340 ms 137148 KB Output is correct
30 Correct 318 ms 137040 KB Output is correct