oj.uz

Submission #860041

# Submission time Handle Problem Language Result Execution time Memory
860041 2023-10-11T12:53:35 Z Alfraganus Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
64 / 100
 3000 ms 215828 KB 
#include <bits/stdc++.h>
using namespace std;
struct tree_type
{
    int s;
    vector<pair<int, int>> arr;
};
vector<tree_type> tree;

vector<int> a;
const int inf = INT_MAX;
void build(int v, int l, int r)
{
    if (l == r)
    {
        tree[v].s = -1;
        tree[v].arr.push_back({a[l - 1], l});
    }
    else
    {
        int m = (l + r) >> 1;
        build(v << 1, l, m);
        build(v << 1 | 1, m + 1, r);
        tree[v] = tree[v << 1];
        tree[v].s = max(tree[v].s, tree[v << 1 | 1].s);

        int mx = inf;

        int i = 0;
        while (i < tree[v << 1 | 1].arr.size() && tree[v << 1 | 1].arr[i] < tree[v].arr.back())
            mx = tree[v << 1 | 1].arr[i++].first;

        if (mx != inf)
            tree[v].s = max(tree[v].arr.back().first + mx, tree[v].s);
        while (i < tree[v << 1 | 1].arr.size())
            tree[v].arr.push_back(tree[v << 1 | 1].arr[i++]);
    }
}
int get(int v, int l, int r, int L, int R, int k)
{
    if (L == l && r == R)
    {
        if (tree[v].s > k)
            throw 1;
        return tree[v].arr.back().first;
    }
    int m = (l + r) >> 1;
    if (R <= m)
        return get(v << 1, l, m, L, R, k);
    else if (m < L)
        return get(v << 1 | 1, m + 1, r, L, R, k);
    else
    {
        int left = get(v << 1, l, m, L, m, k);
        int right = get(v << 1 | 1, m + 1, r, m + 1, R, k);
        if (left * 2 > k)
        {
            auto id = upper_bound(tree[v << 1 | 1].arr.begin(), tree[v << 1 | 1].arr.end(), make_pair(k - left, inf));
            if (id != tree[v << 1 | 1].arr.end() && id->second <= R && left > id->first)
                throw 1;
        }
        return max(left, right);
    }
}
int main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, q;
    cin >> n >> q;
    a.resize(n);
    tree.resize(n << 2);
    for (int &x : a)
        cin >> x;
    build(1, 1, n);
    for (int i = 0, l, r, k; i < q; i++)
    {
        cin >> l >> r >> k;
        try
        {
            int x = get(1, 1, n, l, r, k);
            cout << "1\n";
        }
        catch (int x)
        {
            cout << "0\n";
        }
    }
    return 0;
}

Compilation message

sortbooks.cpp: In function 'void build(int, int, int)':
sortbooks.cpp:30:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |         while (i < tree[v << 1 | 1].arr.size() && tree[v << 1 | 1].arr[i] < tree[v].arr.back())
      |                ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:35:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |         while (i < tree[v << 1 | 1].arr.size())
      |                ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:80:17: warning: unused variable 'x' [-Wunused-variable]
   80 |             int x = get(1, 1, n, l, r, k);
      |                 ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 4 ms 604 KB Output is correct
7 Correct 4 ms 604 KB Output is correct
8 Correct 3 ms 604 KB Output is correct
9 Correct 3 ms 600 KB Output is correct
10 Correct 3 ms 600 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 4 ms 604 KB Output is correct
7 Correct 4 ms 604 KB Output is correct
8 Correct 3 ms 604 KB Output is correct
9 Correct 3 ms 600 KB Output is correct
10 Correct 3 ms 600 KB Output is correct
11 Correct 15 ms 860 KB Output is correct
12 Correct 16 ms 1372 KB Output is correct
13 Correct 19 ms 1520 KB Output is correct
14 Correct 29 ms 1628 KB Output is correct
15 Correct 29 ms 1628 KB Output is correct
16 Correct 13 ms 1876 KB Output is correct
17 Correct 9 ms 1628 KB Output is correct
18 Correct 14 ms 1956 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3057 ms 215828 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 565 ms 22376 KB Output is correct
2 Correct 640 ms 22324 KB Output is correct
3 Correct 102 ms 33804 KB Output is correct
4 Correct 124 ms 33800 KB Output is correct
5 Correct 96 ms 34028 KB Output is correct
6 Correct 284 ms 33796 KB Output is correct
7 Correct 281 ms 33544 KB Output is correct
8 Correct 276 ms 32320 KB Output is correct
9 Correct 117 ms 2132 KB Output is correct
10 Correct 309 ms 32656 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 4 ms 604 KB Output is correct
7 Correct 4 ms 604 KB Output is correct
8 Correct 3 ms 604 KB Output is correct
9 Correct 3 ms 600 KB Output is correct
10 Correct 3 ms 600 KB Output is correct
11 Correct 15 ms 860 KB Output is correct
12 Correct 16 ms 1372 KB Output is correct
13 Correct 19 ms 1520 KB Output is correct
14 Correct 29 ms 1628 KB Output is correct
15 Correct 29 ms 1628 KB Output is correct
16 Correct 13 ms 1876 KB Output is correct
17 Correct 9 ms 1628 KB Output is correct
18 Correct 14 ms 1956 KB Output is correct
19 Correct 1191 ms 46904 KB Output is correct
20 Correct 1221 ms 46920 KB Output is correct
21 Correct 1407 ms 46924 KB Output is correct
22 Correct 1403 ms 46884 KB Output is correct
23 Correct 1381 ms 46940 KB Output is correct
24 Correct 188 ms 71416 KB Output is correct
25 Correct 198 ms 71440 KB Output is correct
26 Correct 231 ms 71672 KB Output is correct
27 Correct 239 ms 71564 KB Output is correct
28 Correct 256 ms 71668 KB Output is correct
29 Correct 268 ms 71688 KB Output is correct
30 Correct 280 ms 71668 KB Output is correct
31 Correct 259 ms 71668 KB Output is correct
32 Correct 279 ms 71992 KB Output is correct
33 Correct 282 ms 71660 KB Output is correct
34 Correct 404 ms 71460 KB Output is correct
35 Correct 405 ms 71260 KB Output is correct
36 Correct 390 ms 70976 KB Output is correct
37 Correct 391 ms 71068 KB Output is correct
38 Correct 410 ms 71160 KB Output is correct
39 Correct 523 ms 62068 KB Output is correct
40 Correct 314 ms 46008 KB Output is correct
41 Correct 627 ms 67408 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 4 ms 604 KB Output is correct
7 Correct 4 ms 604 KB Output is correct
8 Correct 3 ms 604 KB Output is correct
9 Correct 3 ms 600 KB Output is correct
10 Correct 3 ms 600 KB Output is correct
11 Correct 15 ms 860 KB Output is correct
12 Correct 16 ms 1372 KB Output is correct
13 Correct 19 ms 1520 KB Output is correct
14 Correct 29 ms 1628 KB Output is correct
15 Correct 29 ms 1628 KB Output is correct
16 Correct 13 ms 1876 KB Output is correct
17 Correct 9 ms 1628 KB Output is correct
18 Correct 14 ms 1956 KB Output is correct
19 Execution timed out 3057 ms 215828 KB Time limit exceeded
20 Halted 0 ms 0 KB -