oj.uz

Submission #935138

# Submission time Handle Problem Language Result Execution time Memory
935138 2024-02-28T17:44:11 Z borisAngelov Index (COCI21_index) C++17
110 / 110
 904 ms 208316 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 199888 KB Output is correct
2 Correct 42 ms 199888 KB Output is correct
3 Correct 44 ms 199884 KB Output is correct
4 Correct 45 ms 199760 KB Output is correct
5 Correct 44 ms 199792 KB Output is correct
6 Correct 43 ms 199884 KB Output is correct
7 Correct 44 ms 199888 KB Output is correct
8 Correct 44 ms 199888 KB Output is correct
9 Correct 43 ms 199884 KB Output is correct
10 Correct 42 ms 199732 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 199888 KB Output is correct
2 Correct 42 ms 199888 KB Output is correct
3 Correct 44 ms 199884 KB Output is correct
4 Correct 45 ms 199760 KB Output is correct
5 Correct 44 ms 199792 KB Output is correct
6 Correct 43 ms 199884 KB Output is correct
7 Correct 44 ms 199888 KB Output is correct
8 Correct 44 ms 199888 KB Output is correct
9 Correct 43 ms 199884 KB Output is correct
10 Correct 42 ms 199732 KB Output is correct
11 Correct 210 ms 201440 KB Output is correct
12 Correct 210 ms 201324 KB Output is correct
13 Correct 219 ms 201696 KB Output is correct
14 Correct 210 ms 201412 KB Output is correct
15 Correct 213 ms 201456 KB Output is correct
16 Correct 216 ms 201760 KB Output is correct
17 Correct 208 ms 201416 KB Output is correct
18 Correct 219 ms 201412 KB Output is correct
19 Correct 215 ms 201464 KB Output is correct
20 Correct 210 ms 201412 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 199888 KB Output is correct
2 Correct 42 ms 199888 KB Output is correct
3 Correct 44 ms 199884 KB Output is correct
4 Correct 45 ms 199760 KB Output is correct
5 Correct 44 ms 199792 KB Output is correct
6 Correct 43 ms 199884 KB Output is correct
7 Correct 44 ms 199888 KB Output is correct
8 Correct 44 ms 199888 KB Output is correct
9 Correct 43 ms 199884 KB Output is correct
10 Correct 42 ms 199732 KB Output is correct
11 Correct 210 ms 201440 KB Output is correct
12 Correct 210 ms 201324 KB Output is correct
13 Correct 219 ms 201696 KB Output is correct
14 Correct 210 ms 201412 KB Output is correct
15 Correct 213 ms 201456 KB Output is correct
16 Correct 216 ms 201760 KB Output is correct
17 Correct 208 ms 201416 KB Output is correct
18 Correct 219 ms 201412 KB Output is correct
19 Correct 215 ms 201464 KB Output is correct
20 Correct 210 ms 201412 KB Output is correct
21 Correct 881 ms 206528 KB Output is correct
22 Correct 883 ms 208064 KB Output is correct
23 Correct 876 ms 208064 KB Output is correct
24 Correct 893 ms 208052 KB Output is correct
25 Correct 891 ms 208068 KB Output is correct
26 Correct 904 ms 207996 KB Output is correct
27 Correct 862 ms 208216 KB Output is correct
28 Correct 902 ms 208316 KB Output is correct
29 Correct 870 ms 208252 KB Output is correct
30 Correct 885 ms 208064 KB Output is correct