oj.uz

Submission #498736

# Submission time Handle Problem Language Result Execution time Memory
498736 2021-12-26T09:24:26 Z dxz05 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
34 / 100
 3000 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.first != -1 && rg.first != -1) {
        int x = biggest(1, 1, size, tm + 1, r, 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 2 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 3 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 2 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 2 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 3 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 2 ms 332 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 16 ms 588 KB Output is correct
12 Correct 20 ms 1636 KB Output is correct
13 Correct 24 ms 1644 KB Output is correct
14 Correct 39 ms 1668 KB Output is correct
15 Correct 36 ms 1660 KB Output is correct
16 Correct 29 ms 1656 KB Output is correct
17 Correct 19 ms 1316 KB Output is correct
18 Correct 25 ms 1612 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 506 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 1354 ms 27088 KB Output is correct
2 Correct 1558 ms 27024 KB Output is correct
3 Correct 1071 ms 27044 KB Output is correct
4 Correct 1098 ms 27084 KB Output is correct
5 Correct 1024 ms 27120 KB Output is correct
6 Correct 1206 ms 26980 KB Output is correct
7 Correct 1156 ms 27060 KB Output is correct
8 Correct 831 ms 27060 KB Output is correct
9 Correct 234 ms 632 KB Output is correct
10 Correct 798 ms 27260 KB Output is correct

Subtask #5
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 2 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 3 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 2 ms 332 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 16 ms 588 KB Output is correct
12 Correct 20 ms 1636 KB Output is correct
13 Correct 24 ms 1644 KB Output is correct
14 Correct 39 ms 1668 KB Output is correct
15 Correct 36 ms 1660 KB Output is correct
16 Correct 29 ms 1656 KB Output is correct
17 Correct 19 ms 1316 KB Output is correct
18 Correct 25 ms 1612 KB Output is correct
19 Execution timed out 3073 ms 54748 KB Time limit exceeded
20 Halted 0 ms 0 KB -

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 2 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 3 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 2 ms 332 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 16 ms 588 KB Output is correct
12 Correct 20 ms 1636 KB Output is correct
13 Correct 24 ms 1644 KB Output is correct
14 Correct 39 ms 1668 KB Output is correct
15 Correct 36 ms 1660 KB Output is correct
16 Correct 29 ms 1656 KB Output is correct
17 Correct 19 ms 1316 KB Output is correct
18 Correct 25 ms 1612 KB Output is correct
19 Runtime error 506 ms 262148 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -