oj.uz

Submission #935107

# Submission time Handle Problem Language Result Execution time Memory
935107 2024-02-28T16:13:35 Z borisAngelov Index (COCI21_index) C++17
60 / 110
 2500 ms 52056 KB 
#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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19292 KB Output is correct
2 Correct 8 ms 19292 KB Output is correct
3 Correct 8 ms 19292 KB Output is correct
4 Correct 9 ms 19288 KB Output is correct
5 Correct 9 ms 19288 KB Output is correct
6 Correct 8 ms 19304 KB Output is correct
7 Correct 9 ms 19288 KB Output is correct
8 Correct 9 ms 19292 KB Output is correct
9 Correct 8 ms 19292 KB Output is correct
10 Correct 10 ms 19288 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19292 KB Output is correct
2 Correct 8 ms 19292 KB Output is correct
3 Correct 8 ms 19292 KB Output is correct
4 Correct 9 ms 19288 KB Output is correct
5 Correct 9 ms 19288 KB Output is correct
6 Correct 8 ms 19304 KB Output is correct
7 Correct 9 ms 19288 KB Output is correct
8 Correct 9 ms 19292 KB Output is correct
9 Correct 8 ms 19292 KB Output is correct
10 Correct 10 ms 19288 KB Output is correct
11 Correct 506 ms 26988 KB Output is correct
12 Correct 509 ms 27344 KB Output is correct
13 Correct 503 ms 26828 KB Output is correct
14 Correct 510 ms 26880 KB Output is correct
15 Correct 515 ms 27344 KB Output is correct
16 Correct 497 ms 26828 KB Output is correct
17 Correct 511 ms 26892 KB Output is correct
18 Correct 505 ms 27428 KB Output is correct
19 Correct 502 ms 26924 KB Output is correct
20 Correct 508 ms 27084 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19292 KB Output is correct
2 Correct 8 ms 19292 KB Output is correct
3 Correct 8 ms 19292 KB Output is correct
4 Correct 9 ms 19288 KB Output is correct
5 Correct 9 ms 19288 KB Output is correct
6 Correct 8 ms 19304 KB Output is correct
7 Correct 9 ms 19288 KB Output is correct
8 Correct 9 ms 19292 KB Output is correct
9 Correct 8 ms 19292 KB Output is correct
10 Correct 10 ms 19288 KB Output is correct
11 Correct 506 ms 26988 KB Output is correct
12 Correct 509 ms 27344 KB Output is correct
13 Correct 503 ms 26828 KB Output is correct
14 Correct 510 ms 26880 KB Output is correct
15 Correct 515 ms 27344 KB Output is correct
16 Correct 497 ms 26828 KB Output is correct
17 Correct 511 ms 26892 KB Output is correct
18 Correct 505 ms 27428 KB Output is correct
19 Correct 502 ms 26924 KB Output is correct
20 Correct 508 ms 27084 KB Output is correct
21 Execution timed out 2541 ms 52056 KB Time limit exceeded
22 Halted 0 ms 0 KB -