oj.uz

Submission #501599

# Submission time Handle Problem Language Result Execution time Memory
501599 2022-01-04T07:06:53 Z dxz05 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
64 / 100
 3000 ms 223772 KB 
#pragma GCC optimize("Ofast,O2,O3,unroll-loops")
#pragma GCC target("avx2")

#include <bits/stdc++.h>

using namespace std;

#define SZ(s) ((int)s.size())
#define all(x) (x).begin(), (x).end()
#define lla(x) (x).rbegin(), (x).rend()

#define MP make_pair

inline void merge(vector<int> &v, const vector<int> &a, const vector<int> &b){
    int n = a.size(), m = b.size();
    int i = 0, j = 0;
    while (i < n || j < m){
        if (i < n && (j == m || a[i] < b[j])) v.push_back(a[i++]); else
            v.push_back(b[j++]);
    }
}

#define tree qrisdfni

struct node{
    int ans = 0;
    int mx = -1;
    vector<int> vec;
    node(){};
} tree[2500000];

int size = 1;

inline int lwb(int x, const vector<int> &v){
    int i = lower_bound(all(v), x) - v.begin() - 1;
    if (i >= 0) return v[i];
    return -1;
}

inline void build(int v, int tl, int tr, const vector<int> &a){
    tree[v].vec.reserve(tr - tl + 1);

    if (tl == tr){
        tree[v].ans = 0;
        tree[v].mx = a[tl - 1];
        tree[v].vec = {a[tl - 1]};
        return;
    }

    int tm = (tl + tr) >> 1;
    build(v + v, tl, tm, a);
    build(v + v + 1, tm + 1, tr, a);

    merge(tree[v].vec, tree[v + v].vec, tree[v + v + 1].vec);
    tree[v].mx = max(tree[v + v].mx, tree[v + v + 1].mx);
    tree[v].ans = max(tree[v + v].ans, tree[v + v + 1].ans);

    int x = lwb(tree[v + v].mx, tree[v + v + 1].vec);
    if (x != -1) tree[v].ans = max(tree[v].ans, tree[v + v].mx + x);
}

inline void init(const vector<int> &a){
    size = a.size();
    build(1, 1, size, a);
}

inline int biggest(int v, int tl, int tr, int l, int r, int key){
    if (l <= tl && tr <= r){
        int x = lwb(key, tree[v].vec);
        return (x != -1 ? x : -1);
    }
    if (tl > r || tr < l) return -1;
    int tm = (tl + tr) >> 1;
    return max(biggest(v + v, tl, tm, l, r, key), biggest(v + v + 1, tm + 1, tr, l, r, key));
}

inline pair<int, int> get(int v, int tl, int tr, int l, int r){
    if (l <= tl && tr <= r) return MP(tree[v].ans, tree[v].mx);
    if (tl > r || tr < l) return MP(0, -1);
    int tm = (tl + tr) >> 1;
    auto lf = get(v + v, tl, tm, l, r), rg = get(v + v + 1, tm + 1, tr, l, r);
    int ans = max(lf.first, rg.first);
    if (lf.second != -1 && rg.second != -1) {
        int x = biggest(1, 1, size, tm + 1, min(r, tr), lf.second);
        if (x != -1) ans = max(ans, lf.second + x);
    }

    return MP(ans, max(lf.second, rg.second));
}

inline int get(int l, int r){
    return get(1, 1, size, l, r).first;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

    int n, q;
    cin >> n >> q;

    vector<int> a(n);
    for (int &i : a) cin >> i;

    init(a);

    while (q--) {
        int l, r, k;
        cin >> l >> r >> k;
        cout << (get(l, r) <= k) << endl;
    }

    return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 78556 KB Output is correct
2 Correct 37 ms 78556 KB Output is correct
3 Correct 38 ms 78516 KB Output is correct
4 Correct 48 ms 78536 KB Output is correct
5 Correct 38 ms 78548 KB Output is correct
6 Correct 48 ms 78636 KB Output is correct
7 Correct 39 ms 78552 KB Output is correct
8 Correct 39 ms 78620 KB Output is correct
9 Correct 40 ms 78572 KB Output is correct
10 Correct 40 ms 78544 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 78556 KB Output is correct
2 Correct 37 ms 78556 KB Output is correct
3 Correct 38 ms 78516 KB Output is correct
4 Correct 48 ms 78536 KB Output is correct
5 Correct 38 ms 78548 KB Output is correct
6 Correct 48 ms 78636 KB Output is correct
7 Correct 39 ms 78552 KB Output is correct
8 Correct 39 ms 78620 KB Output is correct
9 Correct 40 ms 78572 KB Output is correct
10 Correct 40 ms 78544 KB Output is correct
11 Correct 48 ms 78632 KB Output is correct
12 Correct 49 ms 79000 KB Output is correct
13 Correct 55 ms 79064 KB Output is correct
14 Correct 58 ms 79080 KB Output is correct
15 Correct 60 ms 79020 KB Output is correct
16 Correct 52 ms 79020 KB Output is correct
17 Correct 49 ms 78868 KB Output is correct
18 Correct 51 ms 79048 KB Output is correct

Subtask #3
0 / 13.0

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

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 571 ms 90564 KB Output is correct
2 Correct 630 ms 90664 KB Output is correct
3 Correct 570 ms 90596 KB Output is correct
4 Correct 526 ms 90604 KB Output is correct
5 Correct 545 ms 90620 KB Output is correct
6 Correct 555 ms 90644 KB Output is correct
7 Correct 553 ms 90676 KB Output is correct
8 Correct 448 ms 90648 KB Output is correct
9 Correct 217 ms 78780 KB Output is correct
10 Correct 432 ms 90760 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 78556 KB Output is correct
2 Correct 37 ms 78556 KB Output is correct
3 Correct 38 ms 78516 KB Output is correct
4 Correct 48 ms 78536 KB Output is correct
5 Correct 38 ms 78548 KB Output is correct
6 Correct 48 ms 78636 KB Output is correct
7 Correct 39 ms 78552 KB Output is correct
8 Correct 39 ms 78620 KB Output is correct
9 Correct 40 ms 78572 KB Output is correct
10 Correct 40 ms 78544 KB Output is correct
11 Correct 48 ms 78632 KB Output is correct
12 Correct 49 ms 79000 KB Output is correct
13 Correct 55 ms 79064 KB Output is correct
14 Correct 58 ms 79080 KB Output is correct
15 Correct 60 ms 79020 KB Output is correct
16 Correct 52 ms 79020 KB Output is correct
17 Correct 49 ms 78868 KB Output is correct
18 Correct 51 ms 79048 KB Output is correct
19 Correct 1229 ms 103536 KB Output is correct
20 Correct 1271 ms 103664 KB Output is correct
21 Correct 1272 ms 103548 KB Output is correct
22 Correct 1318 ms 103516 KB Output is correct
23 Correct 1281 ms 103512 KB Output is correct
24 Correct 1178 ms 103528 KB Output is correct
25 Correct 1200 ms 103636 KB Output is correct
26 Correct 1211 ms 103568 KB Output is correct
27 Correct 1194 ms 103568 KB Output is correct
28 Correct 1223 ms 103480 KB Output is correct
29 Correct 1149 ms 103532 KB Output is correct
30 Correct 1228 ms 103524 KB Output is correct
31 Correct 1285 ms 103584 KB Output is correct
32 Correct 1347 ms 103528 KB Output is correct
33 Correct 1530 ms 103500 KB Output is correct
34 Correct 1422 ms 103516 KB Output is correct
35 Correct 1416 ms 103484 KB Output is correct
36 Correct 1317 ms 103444 KB Output is correct
37 Correct 1257 ms 103440 KB Output is correct
38 Correct 1256 ms 103464 KB Output is correct
39 Correct 1114 ms 103524 KB Output is correct
40 Correct 800 ms 94816 KB Output is correct
41 Correct 958 ms 103520 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 78556 KB Output is correct
2 Correct 37 ms 78556 KB Output is correct
3 Correct 38 ms 78516 KB Output is correct
4 Correct 48 ms 78536 KB Output is correct
5 Correct 38 ms 78548 KB Output is correct
6 Correct 48 ms 78636 KB Output is correct
7 Correct 39 ms 78552 KB Output is correct
8 Correct 39 ms 78620 KB Output is correct
9 Correct 40 ms 78572 KB Output is correct
10 Correct 40 ms 78544 KB Output is correct
11 Correct 48 ms 78632 KB Output is correct
12 Correct 49 ms 79000 KB Output is correct
13 Correct 55 ms 79064 KB Output is correct
14 Correct 58 ms 79080 KB Output is correct
15 Correct 60 ms 79020 KB Output is correct
16 Correct 52 ms 79020 KB Output is correct
17 Correct 49 ms 78868 KB Output is correct
18 Correct 51 ms 79048 KB Output is correct
19 Execution timed out 3075 ms 223772 KB Time limit exceeded
20 Halted 0 ms 0 KB -