Submission #440146

#	Time	Username	Problem	Language	Result	Execution time	Memory
440146		FatihSolak	Index (COCI21_index)	C++17	110 / 110	2380 ms	134304 KiB

index

#include <bits/stdc++.h>
#define N 200005
using namespace std;
int arr[N];
int cnt[N];
struct Node{
    int sum;
    Node *lc,*rc;
    Node(int a){
        sum = a;
    }
    Node(Node *a, Node *b){
        sum = a->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 mt;
int get(Node* v1,Node* v2,int tl,int tr, int l){
    if(tr <  l){
        return 0;
    }
    if(l <= tl){
        return v1->sum - v2 -> sum;
    }
    mt  = (tl+tr)/2;
    return get(v1->lc,v2->lc,tl,mt,l) + get(v1->rc,v2->rc,mt+1,tr,l);
}
int get(Node* v,int tl,int tr, int l){
    if(tr <  l){
        return 0;
    }
    if(l <= tl){
        return v->sum;
    }
    mt = (tl+tr)/2;
    return get(v->lc,tl,mt,l) + get(v->rc,mt+1,tr,l);
}
Node* roots[N];
int main(){
    int n,q;
    scanf("%d%d",&n,&q);
    for(int i=0;i<n;i++){
        scanf("%d",&arr[i]);
        cnt[arr[i]]++;
    }
    roots[0] = build(1,N-1);
    for(int i=1;i<n;i++){
        roots[i] = upd(roots[i-1],1,N-1,arr[i-1],-1);
    }
    int ql,qr;
    int l,r,m,val;
    while(q--){
        scanf("%d%d",&ql,&qr);
        ql--,qr--;
        l = 1,r = qr-ql+1;
        while(l < r){
            m = (l+r+1)/2;
            if(qr +1 != n){
                val = get(roots[ql],roots[qr+1],1,N-1,m);
            }
            else val = get(roots[ql],1,N-1,m);
            if(val >= m){
                l = m;
            }
            else r = m-1;
        }
        printf("%d\n",l);
    }
}

Compilation message (stderr)

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

• Subtask 1: 20 / 20
• Subtask 2: 40 / 40
• Subtask 3: 50 / 50