Submission #1211889

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211889		NHristov	Index (COCI21_index)	C++20	110 / 110	130 ms	6160 KiB

index

#include <bits/stdc++.h>
#define endl '\n'

using namespace std;

const int BLOCK = 100;

const int N = 2e5 + 5;
const int Q = 2e5 + 5;

struct Query
{
    int l, r, id;

    bool operator < (const Query &other)
    {
        if (l / BLOCK == other.l / BLOCK)
        {
            if ((l / BLOCK) & 1)
            {
                return r < other.r;
            }

            return r > other.r;
        }

        return l < other.l;
    }
};

int n, t;
int p[N];
Query queries[Q];

int ans[Q];
int times[N];

int all;
int curr;

void add(int x)
{
    times[x]++;

    if (x >= curr)
    {
        all++;
    }

    if (all - times[curr] > curr)
    {
        all -= times[curr];
        curr++;
    }
}

void rem(int x)
{
    times[x]--;

    if (x >= curr)
    {
        all--;
    }

    if (all < curr)
    {
        curr--;
        all += times[curr];
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> t;

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

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

        queries[i].id = i;
    }

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

    int l = 1, r = 0;

    for (int i = 1; i <= t; i++)
    {
        while (r < queries[i].r)
        {
            r++;
            add(p[r]);
        }

        while (l > queries[i].l)
        {
            l--;
            add(p[l]);
        }

        while (r > queries[i].r)
        {
            rem(p[r]);
            r--;
        }

        while (l < queries[i].l)
        {
            rem(p[l]);
            l++;
        }

        ans[queries[i].id] = curr;
    }

    for (int i = 1; i <= t; i++)
    {
        cout << ans[i] << endl;
    }

    return 0;
}

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