oj.uz

Submission #404031

# Submission time Handle Problem Language Result Execution time Memory
404031 2021-05-13T17:07:58 Z ScarletS Index (COCI21_index) C++17
110 / 110
 1087 ms 111608 KB 
#include <bits/stdc++.h>
#define ll long long
using namespace std;

struct pst {
    struct node {
        int val;
        node *l, *r;
        node(ll x) : val(x) {}
    };
    deque<node> buffer;
    node *newnode(int x = 0) {
        buffer.emplace_back(x);
        return &buffer.back();
    }
    node *merge(node *l, node *r) {
        auto x = newnode(l->val + r->val);
        x->l = l, x->r = r;
        return x;
    }
    int n, a=0;
    node *roots[200005];
    pst(int n) : n(n) {roots[0] = build(1, n);}
    node *build(int l, int r) {
        if(l == r) 
            return newnode();
        return merge(build(l,(l+r)>>1),build((l+r+2)>>1, r));
    }
    node *update(node *v, int l, int r, int i, int x) {
        if(r < i || i < l)
            return v;
        if(l == r)
            return newnode(v->val+x);
        return merge(update(v->l,l,(l+r)>>1,i,x), update(v->r,(l+r+2)>>1,r,i,x));
    }
    void update(int k, int i, int x) {
        roots[k] = update(roots[k], 1, n, i, x);
    }
    ll query(node *v, int cL, int cR, int l, int r) {
        if (r<cL||cR<l)
            return 0;
        if (l<=cL&&cR<=r)
            return v->val;
        return query(v->l,cL,(cL+cR)>>1,l,r) + query(v->r,(cL+cR+2)>>1,cR,l,r);
    }
    ll query(int k, int l, int r) {
        return query(roots[k],1,n,l,r);
    }
    void clone(int k) {
        roots[++a] = merge(roots[k]->l, roots[k]->r);
        roots[a]->val = roots[k]->val;
    }
};

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n,q,x,L,R,l,r,m;
    cin>>n>>q;
    pst seg(n);
    for (int i=1;i<=n;++i)
    {
        cin>>x;
        seg.clone(i-1);
        seg.update(i,x,1);
    }
    while (q--)
    {
        cin>>L>>R;
        l=1;r=n;
        while (l<r)
        {
            m=l+(r-l)/2+1;
            x = seg.query(R,m,n) - seg.query(L-1,m,n);
            if (x<m)
                r=m-1;
            else
                l=m;
        }
        cout<<l<<"\n";
    }
    return 0;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2124 KB Output is correct
2 Correct 3 ms 2124 KB Output is correct
3 Correct 3 ms 2124 KB Output is correct
4 Correct 4 ms 2124 KB Output is correct
5 Correct 3 ms 2124 KB Output is correct
6 Correct 3 ms 2124 KB Output is correct
7 Correct 3 ms 2136 KB Output is correct
8 Correct 3 ms 2124 KB Output is correct
9 Correct 3 ms 2124 KB Output is correct
10 Correct 3 ms 2124 KB Output is correct
11 Correct 199 ms 26784 KB Output is correct
12 Correct 164 ms 26808 KB Output is correct
13 Correct 190 ms 26752 KB Output is correct
14 Correct 186 ms 26764 KB Output is correct
15 Correct 176 ms 26816 KB Output is correct
16 Correct 173 ms 26760 KB Output is correct
17 Correct 163 ms 26800 KB Output is correct
18 Correct 176 ms 26764 KB Output is correct
19 Correct 167 ms 26828 KB Output is correct
20 Correct 161 ms 26764 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2124 KB Output is correct
2 Correct 3 ms 2124 KB Output is correct
3 Correct 3 ms 2124 KB Output is correct
4 Correct 4 ms 2124 KB Output is correct
5 Correct 3 ms 2124 KB Output is correct
6 Correct 3 ms 2124 KB Output is correct
7 Correct 3 ms 2136 KB Output is correct
8 Correct 3 ms 2124 KB Output is correct
9 Correct 3 ms 2124 KB Output is correct
10 Correct 3 ms 2124 KB Output is correct
11 Correct 199 ms 26784 KB Output is correct
12 Correct 164 ms 26808 KB Output is correct
13 Correct 190 ms 26752 KB Output is correct
14 Correct 186 ms 26764 KB Output is correct
15 Correct 176 ms 26816 KB Output is correct
16 Correct 173 ms 26760 KB Output is correct
17 Correct 163 ms 26800 KB Output is correct
18 Correct 176 ms 26764 KB Output is correct
19 Correct 167 ms 26828 KB Output is correct
20 Correct 161 ms 26764 KB Output is correct
21 Correct 1087 ms 111608 KB Output is correct
22 Correct 1006 ms 111296 KB Output is correct
23 Correct 996 ms 110344 KB Output is correct
24 Correct 949 ms 110340 KB Output is correct
25 Correct 900 ms 110260 KB Output is correct
26 Correct 909 ms 110404 KB Output is correct
27 Correct 906 ms 110348 KB Output is correct
28 Correct 901 ms 110488 KB Output is correct
29 Correct 910 ms 110260 KB Output is correct
30 Correct 1002 ms 110364 KB Output is correct