oj.uz

Submission #860043

# Submission time Handle Problem Language Result Execution time Memory
860043 2023-10-11T13:02:27 Z Alfraganus Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
77 / 100
 3000 ms 243528 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);
    int mn = 1e9;
    for (int &x : a)
        cin >> x, mn = min(mn, x);
    vector<pair<pair<int, int>, int>> que(q);
    bool sub3 = 1;
    for (int i = 0; i < q; i++){
        cin >> que[i].first.first >> que[i].first.second >> que[i].second;
        sub3 &= (que[i].second < mn);
    }
    if(sub3){
        vector<int> dp(n);
        for (int i = 0; i < n - 1; i++)
            dp[i + 1] = a[i + 1] < a[i];
        for (int i = 1; i < n; i++)
            dp[i] += dp[i - 1];
        for(int i = 0; i < q; i ++)
            cout << (dp[que[i].first.first - 1] == dp[que[i].first.second - 1]) << endl;
        return 0;
    }
    tree.resize(n << 2);
    build(1, 1, n);
    for (int i = 0, l, r, k; i < q; i++)
    {
        l = que[i].first.first, r = que[i].first.second, k = que[i].second;
        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:97:17: warning: unused variable 'x' [-Wunused-variable]
   97 |             int x = get(1, 1, n, l, r, k);
      |                 ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 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 624 KB Output is correct
7 Correct 4 ms 624 KB Output is correct
8 Correct 3 ms 604 KB Output is correct
9 Correct 2 ms 348 KB Output is correct
10 Correct 3 ms 604 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 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 624 KB Output is correct
7 Correct 4 ms 624 KB Output is correct
8 Correct 3 ms 604 KB Output is correct
9 Correct 2 ms 348 KB Output is correct
10 Correct 3 ms 604 KB Output is correct
11 Correct 15 ms 680 KB Output is correct
12 Correct 16 ms 1372 KB Output is correct
13 Correct 20 ms 1372 KB Output is correct
14 Correct 28 ms 1372 KB Output is correct
15 Correct 28 ms 1560 KB Output is correct
16 Correct 12 ms 1884 KB Output is correct
17 Correct 9 ms 1880 KB Output is correct
18 Correct 14 ms 1936 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1370 ms 22100 KB Output is correct
2 Correct 1387 ms 55032 KB Output is correct
3 Correct 1374 ms 54864 KB Output is correct
4 Correct 1382 ms 54832 KB Output is correct
5 Correct 1364 ms 54796 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 522 ms 21584 KB Output is correct
2 Correct 605 ms 21640 KB Output is correct
3 Correct 100 ms 33032 KB Output is correct
4 Correct 97 ms 33040 KB Output is correct
5 Correct 98 ms 33032 KB Output is correct
6 Correct 275 ms 33068 KB Output is correct
7 Correct 276 ms 32916 KB Output is correct
8 Correct 277 ms 31784 KB Output is correct
9 Correct 117 ms 1880 KB Output is correct
10 Correct 275 ms 32140 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 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 624 KB Output is correct
7 Correct 4 ms 624 KB Output is correct
8 Correct 3 ms 604 KB Output is correct
9 Correct 2 ms 348 KB Output is correct
10 Correct 3 ms 604 KB Output is correct
11 Correct 15 ms 680 KB Output is correct
12 Correct 16 ms 1372 KB Output is correct
13 Correct 20 ms 1372 KB Output is correct
14 Correct 28 ms 1372 KB Output is correct
15 Correct 28 ms 1560 KB Output is correct
16 Correct 12 ms 1884 KB Output is correct
17 Correct 9 ms 1880 KB Output is correct
18 Correct 14 ms 1936 KB Output is correct
19 Correct 1123 ms 43092 KB Output is correct
20 Correct 1127 ms 42684 KB Output is correct
21 Correct 1312 ms 42580 KB Output is correct
22 Correct 1325 ms 43256 KB Output is correct
23 Correct 1321 ms 42580 KB Output is correct
24 Correct 189 ms 67916 KB Output is correct
25 Correct 187 ms 67320 KB Output is correct
26 Correct 225 ms 67500 KB Output is correct
27 Correct 235 ms 67408 KB Output is correct
28 Correct 254 ms 67520 KB Output is correct
29 Correct 256 ms 67316 KB Output is correct
30 Correct 264 ms 67500 KB Output is correct
31 Correct 260 ms 67428 KB Output is correct
32 Correct 266 ms 67724 KB Output is correct
33 Correct 263 ms 67376 KB Output is correct
34 Correct 391 ms 68088 KB Output is correct
35 Correct 392 ms 67476 KB Output is correct
36 Correct 391 ms 67552 KB Output is correct
37 Correct 387 ms 67504 KB Output is correct
38 Correct 396 ms 67604 KB Output is correct
39 Correct 500 ms 59388 KB Output is correct
40 Correct 312 ms 43976 KB Output is correct
41 Correct 583 ms 65288 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 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 624 KB Output is correct
7 Correct 4 ms 624 KB Output is correct
8 Correct 3 ms 604 KB Output is correct
9 Correct 2 ms 348 KB Output is correct
10 Correct 3 ms 604 KB Output is correct
11 Correct 15 ms 680 KB Output is correct
12 Correct 16 ms 1372 KB Output is correct
13 Correct 20 ms 1372 KB Output is correct
14 Correct 28 ms 1372 KB Output is correct
15 Correct 28 ms 1560 KB Output is correct
16 Correct 12 ms 1884 KB Output is correct
17 Correct 9 ms 1880 KB Output is correct
18 Correct 14 ms 1936 KB Output is correct
19 Correct 1370 ms 22100 KB Output is correct
20 Correct 1387 ms 55032 KB Output is correct
21 Correct 1374 ms 54864 KB Output is correct
22 Correct 1382 ms 54832 KB Output is correct
23 Correct 1364 ms 54796 KB Output is correct
24 Correct 522 ms 21584 KB Output is correct
25 Correct 605 ms 21640 KB Output is correct
26 Correct 100 ms 33032 KB Output is correct
27 Correct 97 ms 33040 KB Output is correct
28 Correct 98 ms 33032 KB Output is correct
29 Correct 275 ms 33068 KB Output is correct
30 Correct 276 ms 32916 KB Output is correct
31 Correct 277 ms 31784 KB Output is correct
32 Correct 117 ms 1880 KB Output is correct
33 Correct 275 ms 32140 KB Output is correct
34 Correct 1123 ms 43092 KB Output is correct
35 Correct 1127 ms 42684 KB Output is correct
36 Correct 1312 ms 42580 KB Output is correct
37 Correct 1325 ms 43256 KB Output is correct
38 Correct 1321 ms 42580 KB Output is correct
39 Correct 189 ms 67916 KB Output is correct
40 Correct 187 ms 67320 KB Output is correct
41 Correct 225 ms 67500 KB Output is correct
42 Correct 235 ms 67408 KB Output is correct
43 Correct 254 ms 67520 KB Output is correct
44 Correct 256 ms 67316 KB Output is correct
45 Correct 264 ms 67500 KB Output is correct
46 Correct 260 ms 67428 KB Output is correct
47 Correct 266 ms 67724 KB Output is correct
48 Correct 263 ms 67376 KB Output is correct
49 Correct 391 ms 68088 KB Output is correct
50 Correct 392 ms 67476 KB Output is correct
51 Correct 391 ms 67552 KB Output is correct
52 Correct 387 ms 67504 KB Output is correct
53 Correct 396 ms 67604 KB Output is correct
54 Correct 500 ms 59388 KB Output is correct
55 Correct 312 ms 43976 KB Output is correct
56 Correct 583 ms 65288 KB Output is correct
57 Execution timed out 3009 ms 243528 KB Time limit exceeded
58 Halted 0 ms 0 KB -