oj.uz

Submission #498798

# Submission time Handle Problem Language Result Execution time Memory
498798 2021-12-26T11:24:17 Z dxz05 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
64 / 100
 1455 ms 262148 KB 
#pragma GCC optimize("Ofast,O2,O3,unroll-loops")
#pragma GCC target("avx2")

#include <bits/stdc++.h>

using namespace std;

void debug_out() { cerr << endl; }

template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << "[" << H << "]";
    debug_out(T...);
}

#ifdef dddxxz
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

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

clock_t startTime;

double getCurrentTime() {
    return (double) (clock() - startTime) / CLOCKS_PER_SEC;
}

#define MP make_pair

typedef long long ll;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
const double eps = 0.000001;
const int MOD = 998244353;
const int INF = 1000000101;
const long long LLINF = 1223372000000000555;
const int N = 1e6 + 3e2;
const int M = 222;

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++]);
    }
}

struct node{
    int ans;
    int mx;
    vector<int> vec;
    node(){
        ans = 0;
        mx = -1;
        vec.resize(0);
    };
} tree[4 * N];

int size = 1;

inline void build(int v, int tl, int tr, const vector<int> &a){
    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 i = lower_bound(all(tree[v + v + 1].vec), tree[v + v].mx) - tree[v + v + 1].vec.begin() - 1;
    if (i >= 0) tree[v].ans = max(tree[v].ans, tree[v + v].mx + tree[v + v + 1].vec[i]);
}

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 i = lower_bound(all(tree[v].vec), key) - tree[v].vec.begin() - 1;
        return (i >= 0 ? tree[v].vec[i] : -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;
}

void solve(int TC) {
    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;
    }

}

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

#ifdef dddxxz
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    int TC = 1;
    //cin >> TC;

    for (int test = 1; test <= TC; test++) {
        //debug(test);
        //cout << "Case #" << test << ": ";
        solve(test);
    }

    cerr << endl << "Time: " << int(getCurrentTime() * 1000) << " ms" << endl;

    return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 125528 KB Output is correct
2 Correct 79 ms 125480 KB Output is correct
3 Correct 66 ms 125568 KB Output is correct
4 Correct 78 ms 125468 KB Output is correct
5 Correct 76 ms 125536 KB Output is correct
6 Correct 78 ms 125508 KB Output is correct
7 Correct 66 ms 125520 KB Output is correct
8 Correct 65 ms 125580 KB Output is correct
9 Correct 71 ms 125704 KB Output is correct
10 Correct 63 ms 125584 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 125528 KB Output is correct
2 Correct 79 ms 125480 KB Output is correct
3 Correct 66 ms 125568 KB Output is correct
4 Correct 78 ms 125468 KB Output is correct
5 Correct 76 ms 125536 KB Output is correct
6 Correct 78 ms 125508 KB Output is correct
7 Correct 66 ms 125520 KB Output is correct
8 Correct 65 ms 125580 KB Output is correct
9 Correct 71 ms 125704 KB Output is correct
10 Correct 63 ms 125584 KB Output is correct
11 Correct 79 ms 125704 KB Output is correct
12 Correct 81 ms 126148 KB Output is correct
13 Correct 84 ms 126176 KB Output is correct
14 Correct 82 ms 126252 KB Output is correct
15 Correct 93 ms 126276 KB Output is correct
16 Correct 86 ms 126192 KB Output is correct
17 Correct 101 ms 125984 KB Output is correct
18 Correct 90 ms 126172 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 527 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 659 ms 139508 KB Output is correct
2 Correct 701 ms 139324 KB Output is correct
3 Correct 633 ms 139516 KB Output is correct
4 Correct 600 ms 139528 KB Output is correct
5 Correct 539 ms 139388 KB Output is correct
6 Correct 617 ms 139336 KB Output is correct
7 Correct 593 ms 139352 KB Output is correct
8 Correct 518 ms 139284 KB Output is correct
9 Correct 253 ms 125764 KB Output is correct
10 Correct 527 ms 139324 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 125528 KB Output is correct
2 Correct 79 ms 125480 KB Output is correct
3 Correct 66 ms 125568 KB Output is correct
4 Correct 78 ms 125468 KB Output is correct
5 Correct 76 ms 125536 KB Output is correct
6 Correct 78 ms 125508 KB Output is correct
7 Correct 66 ms 125520 KB Output is correct
8 Correct 65 ms 125580 KB Output is correct
9 Correct 71 ms 125704 KB Output is correct
10 Correct 63 ms 125584 KB Output is correct
11 Correct 79 ms 125704 KB Output is correct
12 Correct 81 ms 126148 KB Output is correct
13 Correct 84 ms 126176 KB Output is correct
14 Correct 82 ms 126252 KB Output is correct
15 Correct 93 ms 126276 KB Output is correct
16 Correct 86 ms 126192 KB Output is correct
17 Correct 101 ms 125984 KB Output is correct
18 Correct 90 ms 126172 KB Output is correct
19 Correct 1313 ms 154108 KB Output is correct
20 Correct 1374 ms 154068 KB Output is correct
21 Correct 1323 ms 153964 KB Output is correct
22 Correct 1319 ms 153968 KB Output is correct
23 Correct 1384 ms 153956 KB Output is correct
24 Correct 1295 ms 154052 KB Output is correct
25 Correct 1296 ms 153944 KB Output is correct
26 Correct 1386 ms 153964 KB Output is correct
27 Correct 1455 ms 154100 KB Output is correct
28 Correct 1247 ms 153948 KB Output is correct
29 Correct 1301 ms 154016 KB Output is correct
30 Correct 1202 ms 154012 KB Output is correct
31 Correct 1281 ms 154060 KB Output is correct
32 Correct 1242 ms 153928 KB Output is correct
33 Correct 1295 ms 153864 KB Output is correct
34 Correct 1426 ms 153972 KB Output is correct
35 Correct 1276 ms 153904 KB Output is correct
36 Correct 1415 ms 154012 KB Output is correct
37 Correct 1274 ms 153960 KB Output is correct
38 Correct 1282 ms 154208 KB Output is correct
39 Correct 1090 ms 154088 KB Output is correct
40 Correct 780 ms 142232 KB Output is correct
41 Correct 1093 ms 154048 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 125528 KB Output is correct
2 Correct 79 ms 125480 KB Output is correct
3 Correct 66 ms 125568 KB Output is correct
4 Correct 78 ms 125468 KB Output is correct
5 Correct 76 ms 125536 KB Output is correct
6 Correct 78 ms 125508 KB Output is correct
7 Correct 66 ms 125520 KB Output is correct
8 Correct 65 ms 125580 KB Output is correct
9 Correct 71 ms 125704 KB Output is correct
10 Correct 63 ms 125584 KB Output is correct
11 Correct 79 ms 125704 KB Output is correct
12 Correct 81 ms 126148 KB Output is correct
13 Correct 84 ms 126176 KB Output is correct
14 Correct 82 ms 126252 KB Output is correct
15 Correct 93 ms 126276 KB Output is correct
16 Correct 86 ms 126192 KB Output is correct
17 Correct 101 ms 125984 KB Output is correct
18 Correct 90 ms 126172 KB Output is correct
19 Runtime error 527 ms 262148 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -