oj.uz

Submission #440098

# Submission time Handle Problem Language Result Execution time Memory
440098 2021-07-01T15:20:33 Z FatihSolak Index (COCI21_index) C++17
60 / 110
 2500 ms 138216 KB 
#include <bits/stdc++.h>
#define N 200005
#define int long long
using namespace std;
int arr[N];
int cnt[N];
struct Node{
    int sum=0;
    Node *lc=NULL,*rc=NULL;
    Node(int a){
        sum = a;
    }
    Node(Node *a, Node *b){
        if(a != NULL)sum += a->sum;
        if(b != NULL)sum += b->sum;
        lc = a;
        rc = b;
    }
};
Node* build(int l,int r){
    if(l == r){
        return new Node(cnt[l]);
    }
    int m = (l+r)/2;
    return new Node(build(l,m),build(m+1,r));
}
Node* upd(Node* v,int l,int r,int pos,int val){
    if(l == r){
        return new Node(v->sum + val);
    }
    int m = (l+r)/2;
    if(pos <=m){
        return new Node(upd(v->lc,l,m,pos,val),v->rc);
    }
    else return new Node(v->lc,upd(v->rc,m+1,r,pos,val));
}
int get(Node* v,int tl,int tr, int l,int r){
    if(tr <  l || r < tl){
        return 0;
    }
    if(l <= tl && tr <= r){
        return v->sum;
    }
    int tm  = (tl+tr)/2;
    return get(v->lc,tl,tm,l,r) + get(v->rc,tm+1,tr,l,r);
}
void solve(){
    int n,q;
    cin >> n >> q;
    for(int i=0;i<n;i++){
        cin >> arr[i];
        cnt[arr[i]]++;
    }
    vector<Node *> roots;
    roots.push_back(build(1,N-1));
    for(int i=1;i<n;i++){
        roots.push_back(upd(roots[i-1],1,N-1,arr[i-1],-1));
    }
    while(q--){
        int ql,qr;
        cin >> ql >> qr;
        ql--,qr--;
        int l = 1,r = qr-ql+1;
        while(l < r){
            int m = (l+r+1)/2;
            int val = get(roots[ql],1,N-1,m,N-1);
            if(qr +1 != n){
                val -= get(roots[qr + 1],1,N-1,m,N-1);
            }
            if(val >= m){
                l = m;
            }
            else r = m-1;
        }
        cout << l << endl;
    }
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    #ifdef Local
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    #ifdef Local
    cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 13384 KB Output is correct
2 Correct 25 ms 13416 KB Output is correct
3 Correct 24 ms 13388 KB Output is correct
4 Correct 27 ms 13384 KB Output is correct
5 Correct 25 ms 13380 KB Output is correct
6 Correct 25 ms 13364 KB Output is correct
7 Correct 23 ms 13408 KB Output is correct
8 Correct 24 ms 13364 KB Output is correct
9 Correct 24 ms 13384 KB Output is correct
10 Correct 31 ms 13392 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 13384 KB Output is correct
2 Correct 25 ms 13416 KB Output is correct
3 Correct 24 ms 13388 KB Output is correct
4 Correct 27 ms 13384 KB Output is correct
5 Correct 25 ms 13380 KB Output is correct
6 Correct 25 ms 13364 KB Output is correct
7 Correct 23 ms 13408 KB Output is correct
8 Correct 24 ms 13364 KB Output is correct
9 Correct 24 ms 13384 KB Output is correct
10 Correct 31 ms 13392 KB Output is correct
11 Correct 576 ms 44408 KB Output is correct
12 Correct 665 ms 44440 KB Output is correct
13 Correct 598 ms 44392 KB Output is correct
14 Correct 662 ms 44472 KB Output is correct
15 Correct 615 ms 44504 KB Output is correct
16 Correct 620 ms 44288 KB Output is correct
17 Correct 605 ms 44444 KB Output is correct
18 Correct 642 ms 44348 KB Output is correct
19 Correct 725 ms 44412 KB Output is correct
20 Correct 634 ms 44460 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 13384 KB Output is correct
2 Correct 25 ms 13416 KB Output is correct
3 Correct 24 ms 13388 KB Output is correct
4 Correct 27 ms 13384 KB Output is correct
5 Correct 25 ms 13380 KB Output is correct
6 Correct 25 ms 13364 KB Output is correct
7 Correct 23 ms 13408 KB Output is correct
8 Correct 24 ms 13364 KB Output is correct
9 Correct 24 ms 13384 KB Output is correct
10 Correct 31 ms 13392 KB Output is correct
11 Correct 576 ms 44408 KB Output is correct
12 Correct 665 ms 44440 KB Output is correct
13 Correct 598 ms 44392 KB Output is correct
14 Correct 662 ms 44472 KB Output is correct
15 Correct 615 ms 44504 KB Output is correct
16 Correct 620 ms 44288 KB Output is correct
17 Correct 605 ms 44444 KB Output is correct
18 Correct 642 ms 44348 KB Output is correct
19 Correct 725 ms 44412 KB Output is correct
20 Correct 634 ms 44460 KB Output is correct
21 Execution timed out 2601 ms 138216 KB Time limit exceeded
22 Halted 0 ms 0 KB -