oj.uz

Submission #440121

# Submission time Handle Problem Language Result Execution time Memory
440121 2021-07-01T15:47:11 Z FatihSolak Index (COCI21_index) C++17
60 / 110
 2500 ms 133776 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;
    scanf("%d%d",&n,&q);
    //cin >> n >> q;
    for(int i=0;i<n;i++){
        scanf("%d",&arr[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;
        scanf("%d%d",&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;
        }
        printf("%d\n",l);
        //cout << l << "\n";
    }
}

int32_t main(){
    #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
}

Compilation message

index.cpp: In function 'void solve()':
index.cpp:48:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |     scanf("%d%d",&n,&q);
      |     ~~~~~^~~~~~~~~~~~~~
index.cpp:51:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |         scanf("%d",&arr[i]);
      |         ~~~~~^~~~~~~~~~~~~~
index.cpp:62:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |         scanf("%d%d",&ql,&qr);
      |         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 13348 KB Output is correct
2 Correct 22 ms 13508 KB Output is correct
3 Correct 21 ms 13436 KB Output is correct
4 Correct 29 ms 13380 KB Output is correct
5 Correct 22 ms 13356 KB Output is correct
6 Correct 22 ms 13436 KB Output is correct
7 Correct 22 ms 13436 KB Output is correct
8 Correct 21 ms 13356 KB Output is correct
9 Correct 22 ms 13412 KB Output is correct
10 Correct 21 ms 13388 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 13348 KB Output is correct
2 Correct 22 ms 13508 KB Output is correct
3 Correct 21 ms 13436 KB Output is correct
4 Correct 29 ms 13380 KB Output is correct
5 Correct 22 ms 13356 KB Output is correct
6 Correct 22 ms 13436 KB Output is correct
7 Correct 22 ms 13436 KB Output is correct
8 Correct 21 ms 13356 KB Output is correct
9 Correct 22 ms 13412 KB Output is correct
10 Correct 21 ms 13388 KB Output is correct
11 Correct 534 ms 43160 KB Output is correct
12 Correct 520 ms 43092 KB Output is correct
13 Correct 556 ms 43164 KB Output is correct
14 Correct 529 ms 43128 KB Output is correct
15 Correct 562 ms 43220 KB Output is correct
16 Correct 567 ms 43108 KB Output is correct
17 Correct 573 ms 43216 KB Output is correct
18 Correct 516 ms 43204 KB Output is correct
19 Correct 515 ms 43152 KB Output is correct
20 Correct 520 ms 43048 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 13348 KB Output is correct
2 Correct 22 ms 13508 KB Output is correct
3 Correct 21 ms 13436 KB Output is correct
4 Correct 29 ms 13380 KB Output is correct
5 Correct 22 ms 13356 KB Output is correct
6 Correct 22 ms 13436 KB Output is correct
7 Correct 22 ms 13436 KB Output is correct
8 Correct 21 ms 13356 KB Output is correct
9 Correct 22 ms 13412 KB Output is correct
10 Correct 21 ms 13388 KB Output is correct
11 Correct 534 ms 43160 KB Output is correct
12 Correct 520 ms 43092 KB Output is correct
13 Correct 556 ms 43164 KB Output is correct
14 Correct 529 ms 43128 KB Output is correct
15 Correct 562 ms 43220 KB Output is correct
16 Correct 567 ms 43108 KB Output is correct
17 Correct 573 ms 43216 KB Output is correct
18 Correct 516 ms 43204 KB Output is correct
19 Correct 515 ms 43152 KB Output is correct
20 Correct 520 ms 43048 KB Output is correct
21 Execution timed out 2592 ms 133776 KB Time limit exceeded
22 Halted 0 ms 0 KB -