oj.uz

Submission #440099

# Submission time Handle Problem Language Result Execution time Memory
440099 2021-07-01T15:21:18 Z FatihSolak Index (COCI21_index) C++17
60 / 110
 2500 ms 133904 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 << 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 13380 KB Output is correct
2 Correct 24 ms 13388 KB Output is correct
3 Correct 24 ms 13384 KB Output is correct
4 Correct 23 ms 13336 KB Output is correct
5 Correct 24 ms 13332 KB Output is correct
6 Correct 24 ms 13448 KB Output is correct
7 Correct 24 ms 13388 KB Output is correct
8 Correct 26 ms 13388 KB Output is correct
9 Correct 23 ms 13376 KB Output is correct
10 Correct 23 ms 13460 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 13380 KB Output is correct
2 Correct 24 ms 13388 KB Output is correct
3 Correct 24 ms 13384 KB Output is correct
4 Correct 23 ms 13336 KB Output is correct
5 Correct 24 ms 13332 KB Output is correct
6 Correct 24 ms 13448 KB Output is correct
7 Correct 24 ms 13388 KB Output is correct
8 Correct 26 ms 13388 KB Output is correct
9 Correct 23 ms 13376 KB Output is correct
10 Correct 23 ms 13460 KB Output is correct
11 Correct 603 ms 43104 KB Output is correct
12 Correct 588 ms 43316 KB Output is correct
13 Correct 598 ms 43260 KB Output is correct
14 Correct 578 ms 43364 KB Output is correct
15 Correct 618 ms 43188 KB Output is correct
16 Correct 581 ms 43088 KB Output is correct
17 Correct 598 ms 43384 KB Output is correct
18 Correct 573 ms 43424 KB Output is correct
19 Correct 621 ms 43148 KB Output is correct
20 Correct 583 ms 43324 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 13380 KB Output is correct
2 Correct 24 ms 13388 KB Output is correct
3 Correct 24 ms 13384 KB Output is correct
4 Correct 23 ms 13336 KB Output is correct
5 Correct 24 ms 13332 KB Output is correct
6 Correct 24 ms 13448 KB Output is correct
7 Correct 24 ms 13388 KB Output is correct
8 Correct 26 ms 13388 KB Output is correct
9 Correct 23 ms 13376 KB Output is correct
10 Correct 23 ms 13460 KB Output is correct
11 Correct 603 ms 43104 KB Output is correct
12 Correct 588 ms 43316 KB Output is correct
13 Correct 598 ms 43260 KB Output is correct
14 Correct 578 ms 43364 KB Output is correct
15 Correct 618 ms 43188 KB Output is correct
16 Correct 581 ms 43088 KB Output is correct
17 Correct 598 ms 43384 KB Output is correct
18 Correct 573 ms 43424 KB Output is correct
19 Correct 621 ms 43148 KB Output is correct
20 Correct 583 ms 43324 KB Output is correct
21 Execution timed out 2582 ms 133904 KB Time limit exceeded
22 Halted 0 ms 0 KB -