Submission #1081586

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081586		asli_bg	Index (COCI21_index)	C++11	110 / 110	542 ms	143188 KiB

index

#include<bits/stdc++.h>
using namespace std;

//#define int long long
 
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define pb push_back
 
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef vector<bool> vb;
 
#define sp <<' '<<
#define FOR(i,a) for(int i=0;i<(a);i++)
#define FORE(i,a,b) for(int i=(a);i<(b);i++)

#define cont(x) {for(auto el:x) cout<<el<<' ';cout<<endl;}
#define contp(x) {for(auto el:x) cout<<el.fi<<'-'<<el.se<<' ';cout<<endl;}
#define DEBUG(X) { cout << #X << " = " << (X) << endl; }
 
#define carp(x,y,mod) ((x%mod)*(y%mod))%mod
#define topla(x,y,mod) ((x%mod)+(y%mod))%mod
 
const int MAXN=2e5+5;
const int INF=1e9+1;
#define mid (l+r)/2
#define endl '\n'

int n,q;
vi a;

struct Dug{
    Dug *l;
    Dug *r;
    int sm;

    Dug(int val) : l(nullptr), r(nullptr), sm(val) {}
    Dug(Dug* l, Dug* r) : l(l), r(r), sm(0){
        if(l) sm+=l->sm;
        if(r) sm+=r->sm;
    }
    Dug(Dug* kopya) : l(kopya->l), r(kopya->r), sm(kopya->sm) {}
};

Dug *root[MAXN];

Dug *build(int l=1,int r=n){
    if(l==r) return new Dug(0);
    auto sol=build(l,mid);
    auto sag=build(mid+1,r);
    return new Dug(sol,sag);
}

Dug *update(int pos,int val,Dug* nd,int l=1,int r=n){
    if(l==r){
        return new Dug(val);
    }
    if(pos<=mid){
        auto sol=update(pos,val,nd->l,l,mid);
        return new Dug(sol,nd->r);
    }
    else{
        auto sag=update(pos,val,nd->r,mid+1,r);
        return new Dug(nd->l,sag);
    }
}

int query(int elde,Dug *bir,Dug *iki,int l=1,int r=n){
    if(l==r){
        return l;
    }
    int deg=(iki->r->sm)-(bir->r->sm);
    if(deg>=mid+1-elde) return query(elde,bir->r,iki->r,mid+1,r);
    else return query(elde+deg,bir->l,iki->l,l,mid);
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin>>n>>q;
    a.resize(n+1);
    FORE(i,1,n+1) cin>>a[i];
    root[0]=build();

    map<int,int> cnt;

    FORE(i,1,n+1){
        cnt[a[i]]++;
        root[i]=update(a[i],cnt[a[i]],root[i-1]);
    }

    while(q--){
        int l,r;
        cin>>l>>r;
        cout<<query(0,root[l-1],root[r])<<endl;
    }
}

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