Submission #483896

#	Time	Username	Problem	Language	Result	Execution time	Memory
483896		sam571128	Index (COCI21_index)	C++17	110 / 110	649 ms	11404 KiB

index

#include <bits/stdc++.h>

#define int long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

const int N = 2e5+5;

int k, arr[N], cnt[N], block[N], ans[N], l = 1, r = 0;

struct query{
    int l, r, idx;
    bool operator < (query b){
        if(l/k==b.l/k){
            if((l/k)&1) return r/k < b.r/k;
            return r/k > b.r/k;
        }else{
            return l/k < b.l/k;
        }
    };
};

void add(int idx){
    cnt[arr[idx]]++;
    block[arr[idx]/k]++;
}

void del(int idx){
    cnt[arr[idx]]--;
    block[arr[idx]/k]--;
}

int getans(){
    int now = 0;
    for(int i = N/k;~i;i--){
        if(now+block[i]>=i*k){
            for(int j = (i+1)*k-1;j>=i*k;j--){
                now += cnt[j];
                if(now >= j){
                    return j;
                }
            }
        }
        now += block[i];
    }
    return 0;
}

signed main(){
    fastio
    int n,q;
    cin >> n >> q;
    k = sqrt(n);

    for(int i = 1;i <= n;i++){
        cin >> arr[i];
    }   

    vector<query> Q;

    for(int i = 0;i < q;i++){
        int l,r;
        cin >> l >> r;
        Q.push_back({l,r,i});
    }

    sort(Q.begin(),Q.end());

    for(auto q : Q){
        while(l < q.l) del(l++);
        while(l > q.l) add(--l);
        while(r < q.r) add(++r);
        while(r > q.r) del(r--);
        ans[q.idx] = getans();
    }

    for(int i = 0;i < q;i++){
        cout << ans[i] << "\n";
    }
}

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