Submission #935130

#	Time	Username	Problem	Language	Result	Execution time	Memory
935130		borisAngelov	Index (COCI21_index)	C++17	0 / 110	67 ms	198228 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];
int roots[maxn];
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);

    for (int i = n; i >= 1; --i)
    {
        roots[i] = update(roots[i + 1], 1, n, toAdd[i].second);

        if (tree[roots[i]].sum != n - i + 1)
        {
            return 1;
        }
    }

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

        int l = 1;
        int r = n;

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

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

        cout << toAdd[r].first << "\n";
    }

    return 0;
}

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