Submission #935107

#	Time	Username	Problem	Language	Result	Execution time	Memory
935107		borisAngelov	Index (COCI21_index)	C++17	60 / 110	2541 ms	52056 KiB

index

#include <bits/stdc++.h>

using namespace std;

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

int n, q;

int a[maxn];

vector<int> tree[4 * maxn];

vector<int> combine(const vector<int>& lhs, const vector<int>& rhs)
{
    vector<int> res;

    int lptr = 0;
    int rptr = 0;

    for (int i = 0; i < lhs.size() + rhs.size(); ++i)
    {
        int lnum = (lptr == lhs.size() ? inf : lhs[lptr]);
        int rnum = (rptr == rhs.size() ? inf : rhs[rptr]);

        if (lnum < rnum)
        {
            res.push_back(lnum);
            ++lptr;
        }
        else
        {
            res.push_back(rnum);
            ++rptr;
        }
    }

    return res;
}

void build(int node, int l, int r)
{
    if (l == r)
    {
        tree[node].push_back(a[l]);
        return;
    }

    int mid = (l + r) / 2;

    build(2 * node, l, mid);
    build(2 * node + 1, mid + 1, r);

    tree[node] = combine(tree[2 * node], tree[2 * node + 1]);
}

int query(int node, int l, int r, int ql, int qr, int val)
{
    if (l > qr || r < ql)
    {
        return 0;
    }

    if (ql <= l && r <= qr)
    {
        return tree[node].size() - (lower_bound(tree[node].begin(), tree[node].end(), val) - tree[node].begin());
    }

    int mid = (l + r) / 2;

    return query(2 * node, l, mid, ql, qr, val) + query(2 * node + 1, mid + 1, r, ql, qr, val);
}

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

int main()
{
    fastIO();

    cin >> n >> q;

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

    build(1, 1, n);

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

        int l = 1;
        int r = maxn;

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

            if (query(1, 1, n, from, to, mid) >= mid)
            {
                l = mid + 1;
            }
            else
            {
                r = mid - 1;
            }
        }

        cout << r << "\n";
    }

    return 0;
}

Compilation message (stderr)

index.cpp: In function 'std::vector<int> combine(const std::vector<int>&, const std::vector<int>&)':
index.cpp:21:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for (int i = 0; i < lhs.size() + rhs.size(); ++i)
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~
index.cpp:23:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |         int lnum = (lptr == lhs.size() ? inf : lhs[lptr]);
      |                     ~~~~~^~~~~~~~~~~~~
index.cpp:24:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |         int rnum = (rptr == rhs.size() ? inf : rhs[rptr]);
      |                     ~~~~~^~~~~~~~~~~~~

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