oj.uz

Submission #501597

# Submission time Handle Problem Language Result Execution time Memory
501597 2022-01-04T07:04:15 Z dxz05 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
64 / 100
 3000 ms 262144 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++]);
    }
}

#define tree qrisdfni

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

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;
}

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 59 ms 125548 KB Output is correct
2 Correct 60 ms 125584 KB Output is correct
3 Correct 62 ms 125572 KB Output is correct
4 Correct 59 ms 125508 KB Output is correct
5 Correct 60 ms 125512 KB Output is correct
6 Correct 62 ms 125544 KB Output is correct
7 Correct 64 ms 125524 KB Output is correct
8 Correct 62 ms 125532 KB Output is correct
9 Correct 64 ms 125760 KB Output is correct
10 Correct 64 ms 125564 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 125548 KB Output is correct
2 Correct 60 ms 125584 KB Output is correct
3 Correct 62 ms 125572 KB Output is correct
4 Correct 59 ms 125508 KB Output is correct
5 Correct 60 ms 125512 KB Output is correct
6 Correct 62 ms 125544 KB Output is correct
7 Correct 64 ms 125524 KB Output is correct
8 Correct 62 ms 125532 KB Output is correct
9 Correct 64 ms 125760 KB Output is correct
10 Correct 64 ms 125564 KB Output is correct
11 Correct 81 ms 125784 KB Output is correct
12 Correct 71 ms 126112 KB Output is correct
13 Correct 71 ms 126072 KB Output is correct
14 Correct 82 ms 126184 KB Output is correct
15 Correct 76 ms 126204 KB Output is correct
16 Correct 75 ms 126156 KB Output is correct
17 Correct 72 ms 126092 KB Output is correct
18 Correct 75 ms 126148 KB Output is correct

Subtask #3
0 / 13.0

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

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 586 ms 139628 KB Output is correct
2 Correct 607 ms 139496 KB Output is correct
3 Correct 565 ms 139660 KB Output is correct
4 Correct 549 ms 139556 KB Output is correct
5 Correct 534 ms 139608 KB Output is correct
6 Correct 566 ms 139444 KB Output is correct
7 Correct 560 ms 139636 KB Output is correct
8 Correct 467 ms 139332 KB Output is correct
9 Correct 226 ms 127032 KB Output is correct
10 Correct 446 ms 139332 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 125548 KB Output is correct
2 Correct 60 ms 125584 KB Output is correct
3 Correct 62 ms 125572 KB Output is correct
4 Correct 59 ms 125508 KB Output is correct
5 Correct 60 ms 125512 KB Output is correct
6 Correct 62 ms 125544 KB Output is correct
7 Correct 64 ms 125524 KB Output is correct
8 Correct 62 ms 125532 KB Output is correct
9 Correct 64 ms 125760 KB Output is correct
10 Correct 64 ms 125564 KB Output is correct
11 Correct 81 ms 125784 KB Output is correct
12 Correct 71 ms 126112 KB Output is correct
13 Correct 71 ms 126072 KB Output is correct
14 Correct 82 ms 126184 KB Output is correct
15 Correct 76 ms 126204 KB Output is correct
16 Correct 75 ms 126156 KB Output is correct
17 Correct 72 ms 126092 KB Output is correct
18 Correct 75 ms 126148 KB Output is correct
19 Correct 1225 ms 157172 KB Output is correct
20 Correct 1207 ms 157128 KB Output is correct
21 Correct 1213 ms 156948 KB Output is correct
22 Correct 1222 ms 157040 KB Output is correct
23 Correct 1209 ms 156876 KB Output is correct
24 Correct 1149 ms 157016 KB Output is correct
25 Correct 1163 ms 156956 KB Output is correct
26 Correct 1216 ms 157044 KB Output is correct
27 Correct 1213 ms 157152 KB Output is correct
28 Correct 1224 ms 157036 KB Output is correct
29 Correct 1138 ms 157020 KB Output is correct
30 Correct 1169 ms 157076 KB Output is correct
31 Correct 1179 ms 157244 KB Output is correct
32 Correct 1188 ms 157224 KB Output is correct
33 Correct 1186 ms 157076 KB Output is correct
34 Correct 1201 ms 156844 KB Output is correct
35 Correct 1185 ms 156696 KB Output is correct
36 Correct 1167 ms 156460 KB Output is correct
37 Correct 1189 ms 156660 KB Output is correct
38 Correct 1192 ms 156804 KB Output is correct
39 Correct 1018 ms 155820 KB Output is correct
40 Correct 726 ms 146292 KB Output is correct
41 Correct 945 ms 155156 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 125548 KB Output is correct
2 Correct 60 ms 125584 KB Output is correct
3 Correct 62 ms 125572 KB Output is correct
4 Correct 59 ms 125508 KB Output is correct
5 Correct 60 ms 125512 KB Output is correct
6 Correct 62 ms 125544 KB Output is correct
7 Correct 64 ms 125524 KB Output is correct
8 Correct 62 ms 125532 KB Output is correct
9 Correct 64 ms 125760 KB Output is correct
10 Correct 64 ms 125564 KB Output is correct
11 Correct 81 ms 125784 KB Output is correct
12 Correct 71 ms 126112 KB Output is correct
13 Correct 71 ms 126072 KB Output is correct
14 Correct 82 ms 126184 KB Output is correct
15 Correct 76 ms 126204 KB Output is correct
16 Correct 75 ms 126156 KB Output is correct
17 Correct 72 ms 126092 KB Output is correct
18 Correct 75 ms 126148 KB Output is correct
19 Execution timed out 3016 ms 262144 KB Time limit exceeded
20 Halted 0 ms 0 KB -