oj.uz

Submission #440115

# Submission time Handle Problem Language Result Execution time Memory
440115 2021-07-01T15:40:54 Z FatihSolak Index (COCI21_index) C++17
60 / 110
 2500 ms 133908 KB 
#include <bits/stdc++.h>
#define N 200005
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 << "\n";
    }
}

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 21 ms 13388 KB Output is correct
2 Correct 21 ms 13392 KB Output is correct
3 Correct 22 ms 13452 KB Output is correct
4 Correct 21 ms 13384 KB Output is correct
5 Correct 22 ms 13416 KB Output is correct
6 Correct 21 ms 13336 KB Output is correct
7 Correct 21 ms 13388 KB Output is correct
8 Correct 21 ms 13420 KB Output is correct
9 Correct 23 ms 13400 KB Output is correct
10 Correct 22 ms 13388 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 13388 KB Output is correct
2 Correct 21 ms 13392 KB Output is correct
3 Correct 22 ms 13452 KB Output is correct
4 Correct 21 ms 13384 KB Output is correct
5 Correct 22 ms 13416 KB Output is correct
6 Correct 21 ms 13336 KB Output is correct
7 Correct 21 ms 13388 KB Output is correct
8 Correct 21 ms 13420 KB Output is correct
9 Correct 23 ms 13400 KB Output is correct
10 Correct 22 ms 13388 KB Output is correct
11 Correct 479 ms 43252 KB Output is correct
12 Correct 533 ms 43140 KB Output is correct
13 Correct 461 ms 43068 KB Output is correct
14 Correct 478 ms 43172 KB Output is correct
15 Correct 501 ms 43080 KB Output is correct
16 Correct 537 ms 43264 KB Output is correct
17 Correct 463 ms 43132 KB Output is correct
18 Correct 512 ms 43192 KB Output is correct
19 Correct 463 ms 43104 KB Output is correct
20 Correct 509 ms 43128 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 13388 KB Output is correct
2 Correct 21 ms 13392 KB Output is correct
3 Correct 22 ms 13452 KB Output is correct
4 Correct 21 ms 13384 KB Output is correct
5 Correct 22 ms 13416 KB Output is correct
6 Correct 21 ms 13336 KB Output is correct
7 Correct 21 ms 13388 KB Output is correct
8 Correct 21 ms 13420 KB Output is correct
9 Correct 23 ms 13400 KB Output is correct
10 Correct 22 ms 13388 KB Output is correct
11 Correct 479 ms 43252 KB Output is correct
12 Correct 533 ms 43140 KB Output is correct
13 Correct 461 ms 43068 KB Output is correct
14 Correct 478 ms 43172 KB Output is correct
15 Correct 501 ms 43080 KB Output is correct
16 Correct 537 ms 43264 KB Output is correct
17 Correct 463 ms 43132 KB Output is correct
18 Correct 512 ms 43192 KB Output is correct
19 Correct 463 ms 43104 KB Output is correct
20 Correct 509 ms 43128 KB Output is correct
21 Execution timed out 2591 ms 133908 KB Time limit exceeded
22 Halted 0 ms 0 KB -