Submission #935138

#	Time	Username	Problem	Language	Result	Execution time	Memory
935138		borisAngelov	Index (COCI21_index)	C++17	110 / 110	904 ms	208316 KiB

index

#include <bits/stdc++.h>

using namespace std;

const int maxn = 200005;
const int inf = 1e9;

int n, q;

int a[maxn];
pair<int, int> toAdd[maxn];

struct Node
{
    int lc;
    int rc;
    int sum;

    Node()
    {
        lc = rc = -1;
        sum = 0;
    }
};

Node tree[4 * maxn + 80 * maxn];
vector<pair<int, int>> roots;
int cntNodes = 0;

int update(int node, int l, int r, int pos)
{
    int curr = ++cntNodes;

    if (l == r)
    {
        tree[curr].sum = 1;
        tree[curr].lc = tree[curr].rc = -1;
        return curr;
    }

    tree[curr].lc = tree[node].lc;
    tree[curr].rc = tree[node].rc;

    int mid = (l + r) / 2;

    if (pos <= mid)
    {
        tree[curr].lc = update(tree[curr].lc, l, mid, pos);
    }
    else
    {
        tree[curr].rc = update(tree[curr].rc, mid + 1, r, pos);
    }

    tree[curr].sum = tree[tree[curr].lc].sum + tree[tree[curr].rc].sum;

    return curr;
}

int query(int node, int l, int r, int ql, int qr)
{
    if (ql <= l && r <= qr)
    {
        return tree[node].sum;
    }

    int mid = (l + r) / 2;

    int res = 0;

    if (ql <= mid)
    {
        res += query(tree[node].lc, l, mid, ql, qr);
    }

    if (qr >= mid + 1)
    {
        res += query(tree[node].rc, mid + 1, r, ql, qr);
    }

    return res;
}

void fastIO()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main()
{
    fastIO();

    //freopen("index.txt", "r", stdin);
    //freopen("indexout.txt", "w", stdout);

    cin >> n >> q;

    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
        toAdd[i] = make_pair(a[i], i);
    }

    sort(toAdd + 1, toAdd + n + 1);

    int currnum = 200001;
    roots.push_back(make_pair(0, currnum));

    for (int i = n; i >= 1; --i)
    {
        while (currnum > toAdd[i].first)
        {
            roots.push_back(make_pair(roots.back().first, --currnum));
        }

        if (currnum == toAdd[i].first)
        {
            roots.push_back(make_pair(update(roots.back().first, 1, n, toAdd[i].second), toAdd[i].first));
        }
    }

    reverse(roots.begin(), roots.end());

    for (int i = 1; i <= q; ++i)
    {
        int from, to;
        cin >> from >> to;

        int l = 0;
        int r = roots.size() - 1;

        while (l <= r)
        {
            int mid = (l + r) / 2;

            if (query(roots[mid].first, 1, n, from, to) >= roots[mid].second)
            {
                l = mid + 1;
            }
            else
            {
                r = mid - 1;
            }
        }

        cout << roots[r].second << "\n";
    }

    return 0;
}

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