oj.uz

Submission #237442

# Submission time Handle Problem Language Result Execution time Memory
237442 2020-06-06T15:17:39 Z TeaTime Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
64 / 100
 3000 ms 255044 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <bitset>
#include <unordered_set>
#include <map>
#include <string>
#include <cmath>
#include <queue>
#include <ctime>
#include <set>

using namespace std;

typedef int ll;
typedef long double ld;
#define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
#define pb push_back
#define all(x) (x).begin(),(x).end()

const ll SIZE = 1e6 + 10, INF = 1e9 * 1e9, MOD = 1e9 + 7;

ll tree[SIZE * 4], bst[SIZE * 4];
vector<ll> mrg[SIZE * 4];
vector<ll> vec;

void build(int v, int l, int r) {
    if (l == r - 1) {
        tree[v] = vec[l];
        mrg[v].pb(vec[l]);
        bst[v] = 0;
    }
    else {
        int mid = (l + r) / 2;
        build(v * 2 + 1, l, mid);
        build(v * 2 + 2, mid, r);
        tree[v] = max(tree[v * 2 + 1], tree[v * 2 + 2]);
        merge(mrg[v * 2 + 1].begin(), mrg[v * 2 + 1].end(), mrg[v * 2 + 2].begin(), mrg[v * 2 + 2].end(), std::back_inserter(mrg[v]));
        bst[v] = max(bst[v * 2 + 1], bst[v * 2 + 2]);
        ll q = 0;
        if (lower_bound(mrg[v * 2 + 2].begin(), mrg[v * 2 + 2].end(), tree[v * 2 + 1]) != mrg[v * 2 + 2].begin()) {
            q = *(--lower_bound(mrg[v * 2 + 2].begin(), mrg[v * 2 + 2].end(), tree[v * 2 + 1])) + tree[v * 2 + 1];
        }
        bst[v] = max(bst[v], q);
    }
}

pair<ll, ll> ask(int v, int l, int r, int askl, int askr, ll curMx = -1) {
    if (l >= askr || r <= askl) return { 0, -1 };

    if (l >= askl && r <= askr) {
        ll q = 0;
        if (lower_bound(mrg[v].begin(), mrg[v].end(), curMx) != mrg[v].begin()) {
            q = *(--lower_bound(mrg[v].begin(), mrg[v].end(), curMx)) + curMx;
        }
        return { max(q, bst[v]), tree[v] };
    }

    int mid = (l + r) / 2;
    pair<ll, ll> q = ask(v * 2 + 1, l, mid, askl, askr, curMx), q2 = ask(v * 2 + 2, mid, r, askl, askr, max(curMx, q.second));
    pair<ll, ll> ans;
    ans.first = max(q.first, q2.first);
    ans.second = max(max(q.second, q2.second), curMx);
    return ans;
}

int main() {
    fastInp;

    ll n, m;
    cin >> n >> m;
    vec.resize(n);
    for (int i = 0; i < n; i++) cin >> vec[i];
    build(0, 0, n);

    while (m--) {
        ll l, r, k;
        cin >> l >> r >> k;
        if ((ask(0, 0, n, l - 1, r).first <= k)) {
            cout << "1\n";
        }
        else {
            cout << "0\n";
        }
    }

    return 0;
}

Compilation message

sortbooks.cpp:21:37: warning: overflow in implicit constant conversion [-Woverflow]
 const ll SIZE = 1e6 + 10, INF = 1e9 * 1e9, MOD = 1e9 + 7;
                                 ~~~~^~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 94200 KB Output is correct
2 Correct 58 ms 94328 KB Output is correct
3 Correct 59 ms 94328 KB Output is correct
4 Correct 60 ms 94328 KB Output is correct
5 Correct 61 ms 94332 KB Output is correct
6 Correct 61 ms 94328 KB Output is correct
7 Correct 60 ms 94328 KB Output is correct
8 Correct 64 ms 94328 KB Output is correct
9 Correct 60 ms 94332 KB Output is correct
10 Correct 60 ms 94328 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 94200 KB Output is correct
2 Correct 58 ms 94328 KB Output is correct
3 Correct 59 ms 94328 KB Output is correct
4 Correct 60 ms 94328 KB Output is correct
5 Correct 61 ms 94332 KB Output is correct
6 Correct 61 ms 94328 KB Output is correct
7 Correct 60 ms 94328 KB Output is correct
8 Correct 64 ms 94328 KB Output is correct
9 Correct 60 ms 94332 KB Output is correct
10 Correct 60 ms 94328 KB Output is correct
11 Correct 63 ms 94424 KB Output is correct
12 Correct 64 ms 95096 KB Output is correct
13 Correct 65 ms 95224 KB Output is correct
14 Correct 72 ms 95400 KB Output is correct
15 Correct 67 ms 95224 KB Output is correct
16 Correct 68 ms 95352 KB Output is correct
17 Correct 63 ms 94840 KB Output is correct
18 Correct 65 ms 95224 KB Output is correct

Subtask #3
0 / 13.0

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

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 356 ms 110576 KB Output is correct
2 Correct 314 ms 110704 KB Output is correct
3 Correct 270 ms 110704 KB Output is correct
4 Correct 274 ms 110704 KB Output is correct
5 Correct 281 ms 110704 KB Output is correct
6 Correct 204 ms 110704 KB Output is correct
7 Correct 210 ms 110704 KB Output is correct
8 Correct 250 ms 110708 KB Output is correct
9 Correct 100 ms 95096 KB Output is correct
10 Correct 262 ms 110704 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 94200 KB Output is correct
2 Correct 58 ms 94328 KB Output is correct
3 Correct 59 ms 94328 KB Output is correct
4 Correct 60 ms 94328 KB Output is correct
5 Correct 61 ms 94332 KB Output is correct
6 Correct 61 ms 94328 KB Output is correct
7 Correct 60 ms 94328 KB Output is correct
8 Correct 64 ms 94328 KB Output is correct
9 Correct 60 ms 94332 KB Output is correct
10 Correct 60 ms 94328 KB Output is correct
11 Correct 63 ms 94424 KB Output is correct
12 Correct 64 ms 95096 KB Output is correct
13 Correct 65 ms 95224 KB Output is correct
14 Correct 72 ms 95400 KB Output is correct
15 Correct 67 ms 95224 KB Output is correct
16 Correct 68 ms 95352 KB Output is correct
17 Correct 63 ms 94840 KB Output is correct
18 Correct 65 ms 95224 KB Output is correct
19 Correct 774 ms 127472 KB Output is correct
20 Correct 747 ms 127684 KB Output is correct
21 Correct 638 ms 127596 KB Output is correct
22 Correct 634 ms 127340 KB Output is correct
23 Correct 666 ms 127340 KB Output is correct
24 Correct 429 ms 127344 KB Output is correct
25 Correct 436 ms 127340 KB Output is correct
26 Correct 532 ms 127340 KB Output is correct
27 Correct 527 ms 127340 KB Output is correct
28 Correct 531 ms 127312 KB Output is correct
29 Correct 569 ms 127468 KB Output is correct
30 Correct 580 ms 127340 KB Output is correct
31 Correct 572 ms 127596 KB Output is correct
32 Correct 593 ms 127468 KB Output is correct
33 Correct 591 ms 127468 KB Output is correct
34 Correct 393 ms 127340 KB Output is correct
35 Correct 405 ms 127468 KB Output is correct
36 Correct 387 ms 127212 KB Output is correct
37 Correct 393 ms 127340 KB Output is correct
38 Correct 393 ms 127212 KB Output is correct
39 Correct 515 ms 127340 KB Output is correct
40 Correct 357 ms 113392 KB Output is correct
41 Correct 491 ms 127340 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 94200 KB Output is correct
2 Correct 58 ms 94328 KB Output is correct
3 Correct 59 ms 94328 KB Output is correct
4 Correct 60 ms 94328 KB Output is correct
5 Correct 61 ms 94332 KB Output is correct
6 Correct 61 ms 94328 KB Output is correct
7 Correct 60 ms 94328 KB Output is correct
8 Correct 64 ms 94328 KB Output is correct
9 Correct 60 ms 94332 KB Output is correct
10 Correct 60 ms 94328 KB Output is correct
11 Correct 63 ms 94424 KB Output is correct
12 Correct 64 ms 95096 KB Output is correct
13 Correct 65 ms 95224 KB Output is correct
14 Correct 72 ms 95400 KB Output is correct
15 Correct 67 ms 95224 KB Output is correct
16 Correct 68 ms 95352 KB Output is correct
17 Correct 63 ms 94840 KB Output is correct
18 Correct 65 ms 95224 KB Output is correct
19 Execution timed out 3104 ms 255044 KB Time limit exceeded
20 Halted 0 ms 0 KB -