Submission #494340

#	Time	Username	Problem	Language	Result	Execution time	Memory
494340		AlperenT	Index (COCI21_index)	C++17	110 / 110	488 ms	9924 KiB

index

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5, SQRT = sqrt(N);

int n, q, arr[N], cur, l, r, a, b, cnt[N], cntbig, ans[N];

struct Query{
    int l, r, i;

    bool operator < (const Query &scnd) const{
        if(l / SQRT == scnd.l / SQRT) return r < scnd.r;
        else return l / SQRT < scnd.l / SQRT;
    }
};

Query queries[N];

void fixcur(){
    while(cntbig - cnt[cur] >= cur + 1) cntbig -= cnt[cur], cur++;

    while(cntbig < cur) cur--, cntbig += cnt[cur];
}

int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);

    cin >> n >> q;

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

    for(int i = 1; i <= q; i++){
        cin >> queries[i].l >> queries[i].r;
        queries[i].i = i;
    }

    sort(queries + 1, queries + q + 1);

    a = 0, b = -1;

    for(int i = 1; i <= q; i++){
        l = queries[i].l, r = queries[i].r;

        while(b + 1 <= r){
            b++;
            cnt[arr[b]]++;
            if(arr[b] >= cur) cntbig++;
            fixcur();
        }

        while(b > r){
            cnt[arr[b]]--;
            if(arr[b] >= cur) cntbig--;
            b--;
            fixcur();
        }

        while(a - 1 >= l){
            a--;
            cnt[arr[a]]++;
            if(arr[a] >= cur) cntbig++;
            fixcur();
        }

        while(a < l){
            cnt[arr[a]]--;
            if(arr[a] >= cur) cntbig--;
            a++;
            fixcur();
        }

        ans[queries[i].i] = cur;
    }

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

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