oj.uz

답안 #440126

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
440126 2021-07-01T15:52:48 Z FatihSolak Index (COCI21_index) C++17
60 / 110
 565 ms 269360 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));
    }
    assert(n < 1e5);
    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:63:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |         scanf("%d%d",&ql,&qr);
      |         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 13388 KB Output is correct
2 Correct 21 ms 13376 KB Output is correct
3 Correct 22 ms 13408 KB Output is correct
4 Correct 21 ms 13388 KB Output is correct
5 Correct 22 ms 13324 KB Output is correct
6 Correct 21 ms 13360 KB Output is correct
7 Correct 25 ms 13416 KB Output is correct
8 Correct 25 ms 13388 KB Output is correct
9 Correct 21 ms 13344 KB Output is correct
10 Correct 22 ms 13408 KB Output is correct

Subtask #2
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 13388 KB Output is correct
2 Correct 21 ms 13376 KB Output is correct
3 Correct 22 ms 13408 KB Output is correct
4 Correct 21 ms 13388 KB Output is correct
5 Correct 22 ms 13324 KB Output is correct
6 Correct 21 ms 13360 KB Output is correct
7 Correct 25 ms 13416 KB Output is correct
8 Correct 25 ms 13388 KB Output is correct
9 Correct 21 ms 13344 KB Output is correct
10 Correct 22 ms 13408 KB Output is correct
11 Correct 489 ms 43088 KB Output is correct
12 Correct 528 ms 43168 KB Output is correct
13 Correct 563 ms 43084 KB Output is correct
14 Correct 528 ms 43080 KB Output is correct
15 Correct 502 ms 43096 KB Output is correct
16 Correct 531 ms 43080 KB Output is correct
17 Correct 534 ms 43204 KB Output is correct
18 Correct 535 ms 43256 KB Output is correct
19 Correct 514 ms 43104 KB Output is correct
20 Correct 565 ms 43128 KB Output is correct

Subtask #3
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 13388 KB Output is correct
2 Correct 21 ms 13376 KB Output is correct
3 Correct 22 ms 13408 KB Output is correct
4 Correct 21 ms 13388 KB Output is correct
5 Correct 22 ms 13324 KB Output is correct
6 Correct 21 ms 13360 KB Output is correct
7 Correct 25 ms 13416 KB Output is correct
8 Correct 25 ms 13388 KB Output is correct
9 Correct 21 ms 13344 KB Output is correct
10 Correct 22 ms 13408 KB Output is correct
11 Correct 489 ms 43088 KB Output is correct
12 Correct 528 ms 43168 KB Output is correct
13 Correct 563 ms 43084 KB Output is correct
14 Correct 528 ms 43080 KB Output is correct
15 Correct 502 ms 43096 KB Output is correct
16 Correct 531 ms 43080 KB Output is correct
17 Correct 534 ms 43204 KB Output is correct
18 Correct 535 ms 43256 KB Output is correct
19 Correct 514 ms 43104 KB Output is correct
20 Correct 565 ms 43128 KB Output is correct
21 Runtime error 564 ms 269360 KB Execution killed with signal 6
22 Halted 0 ms 0 KB -