oj.uz

Submission #498793

# Submission time Handle Problem Language Result Execution time Memory
498793 2021-12-26T11:06:34 Z dxz05 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
64 / 100
 1255 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, vector<int> a, 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);
    };
};

int size = 1;

vector<node> tree;

inline void build(int v, int tl, int tr, 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(vector<int> &a){
    size = a.size();
    tree.resize(4 * 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 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 2 ms 332 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 9 ms 588 KB Output is correct
12 Correct 11 ms 1648 KB Output is correct
13 Correct 12 ms 1640 KB Output is correct
14 Correct 18 ms 1612 KB Output is correct
15 Correct 18 ms 1668 KB Output is correct
16 Correct 17 ms 1672 KB Output is correct
17 Correct 13 ms 1228 KB Output is correct
18 Correct 15 ms 1680 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 516 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 567 ms 27084 KB Output is correct
2 Correct 578 ms 27096 KB Output is correct
3 Correct 536 ms 27064 KB Output is correct
4 Correct 521 ms 26980 KB Output is correct
5 Correct 511 ms 27040 KB Output is correct
6 Correct 509 ms 27040 KB Output is correct
7 Correct 517 ms 27068 KB Output is correct
8 Correct 426 ms 27112 KB Output is correct
9 Correct 177 ms 720 KB Output is correct
10 Correct 407 ms 27056 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 9 ms 588 KB Output is correct
12 Correct 11 ms 1648 KB Output is correct
13 Correct 12 ms 1640 KB Output is correct
14 Correct 18 ms 1612 KB Output is correct
15 Correct 18 ms 1668 KB Output is correct
16 Correct 17 ms 1672 KB Output is correct
17 Correct 13 ms 1228 KB Output is correct
18 Correct 15 ms 1680 KB Output is correct
19 Correct 1255 ms 54608 KB Output is correct
20 Correct 1192 ms 54636 KB Output is correct
21 Correct 1169 ms 54628 KB Output is correct
22 Correct 1187 ms 54600 KB Output is correct
23 Correct 1172 ms 54664 KB Output is correct
24 Correct 1157 ms 54636 KB Output is correct
25 Correct 1117 ms 54696 KB Output is correct
26 Correct 1193 ms 54756 KB Output is correct
27 Correct 1188 ms 54624 KB Output is correct
28 Correct 1170 ms 54632 KB Output is correct
29 Correct 1126 ms 54620 KB Output is correct
30 Correct 1123 ms 54616 KB Output is correct
31 Correct 1117 ms 54640 KB Output is correct
32 Correct 1113 ms 54604 KB Output is correct
33 Correct 1189 ms 54764 KB Output is correct
34 Correct 1118 ms 54696 KB Output is correct
35 Correct 1112 ms 54636 KB Output is correct
36 Correct 1122 ms 54668 KB Output is correct
37 Correct 1132 ms 54636 KB Output is correct
38 Correct 1140 ms 54656 KB Output is correct
39 Correct 1010 ms 54576 KB Output is correct
40 Correct 684 ms 33480 KB Output is correct
41 Correct 928 ms 54648 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 9 ms 588 KB Output is correct
12 Correct 11 ms 1648 KB Output is correct
13 Correct 12 ms 1640 KB Output is correct
14 Correct 18 ms 1612 KB Output is correct
15 Correct 18 ms 1668 KB Output is correct
16 Correct 17 ms 1672 KB Output is correct
17 Correct 13 ms 1228 KB Output is correct
18 Correct 15 ms 1680 KB Output is correct
19 Runtime error 516 ms 262148 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -