oj.uz

Submission #498773

# Submission time Handle Problem Language Result Execution time Memory
498773 2021-12-26T10:24:16 Z dxz05 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
77 / 100
 1892 ms 54748 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, 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 cnt[N];

void solve(int TC) {
    int n, q;
    cin >> n >> q;

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

    if (n <= 2e5) {
        init(a);

        while (q--) {
            int l, r, k;
            cin >> l >> r >> k;
            cout << (get(l, r) <= k) << endl;
        }
    } else {
        for (int i = 1; i < n; i++) {
            cnt[i] = cnt[i - 1] + (a[i] < a[i - 1]);
        }

        while (q--) {
            int l, r, k;
            cin >> l >> r >> k;
            cout << (cnt[r - 1] == cnt[l - 1]) << 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 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 2 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 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 2 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 13 ms 588 KB Output is correct
12 Correct 14 ms 1652 KB Output is correct
13 Correct 17 ms 1612 KB Output is correct
14 Correct 27 ms 1612 KB Output is correct
15 Correct 37 ms 1672 KB Output is correct
16 Correct 21 ms 1612 KB Output is correct
17 Correct 14 ms 1228 KB Output is correct
18 Correct 18 ms 1668 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1732 ms 10144 KB Output is correct
2 Correct 1740 ms 10232 KB Output is correct
3 Correct 1676 ms 10152 KB Output is correct
4 Correct 1702 ms 10044 KB Output is correct
5 Correct 1719 ms 10080 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 867 ms 27112 KB Output is correct
2 Correct 793 ms 27112 KB Output is correct
3 Correct 770 ms 27028 KB Output is correct
4 Correct 797 ms 27184 KB Output is correct
5 Correct 723 ms 27076 KB Output is correct
6 Correct 667 ms 27108 KB Output is correct
7 Correct 646 ms 26992 KB Output is correct
8 Correct 579 ms 27140 KB Output is correct
9 Correct 211 ms 560 KB Output is correct
10 Correct 645 ms 26996 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 2 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 13 ms 588 KB Output is correct
12 Correct 14 ms 1652 KB Output is correct
13 Correct 17 ms 1612 KB Output is correct
14 Correct 27 ms 1612 KB Output is correct
15 Correct 37 ms 1672 KB Output is correct
16 Correct 21 ms 1612 KB Output is correct
17 Correct 14 ms 1228 KB Output is correct
18 Correct 18 ms 1668 KB Output is correct
19 Correct 1848 ms 54692 KB Output is correct
20 Correct 1892 ms 54620 KB Output is correct
21 Correct 1615 ms 54700 KB Output is correct
22 Correct 1666 ms 54668 KB Output is correct
23 Correct 1634 ms 54620 KB Output is correct
24 Correct 1494 ms 54620 KB Output is correct
25 Correct 1647 ms 54624 KB Output is correct
26 Correct 1699 ms 54616 KB Output is correct
27 Correct 1685 ms 54588 KB Output is correct
28 Correct 1652 ms 54692 KB Output is correct
29 Correct 1623 ms 54644 KB Output is correct
30 Correct 1598 ms 54620 KB Output is correct
31 Correct 1731 ms 54632 KB Output is correct
32 Correct 1670 ms 54640 KB Output is correct
33 Correct 1772 ms 54716 KB Output is correct
34 Correct 1451 ms 54620 KB Output is correct
35 Correct 1390 ms 54616 KB Output is correct
36 Correct 1411 ms 54708 KB Output is correct
37 Correct 1399 ms 54584 KB Output is correct
38 Correct 1366 ms 54748 KB Output is correct
39 Correct 1338 ms 54708 KB Output is correct
40 Correct 965 ms 33536 KB Output is correct
41 Correct 1337 ms 54660 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 2 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 13 ms 588 KB Output is correct
12 Correct 14 ms 1652 KB Output is correct
13 Correct 17 ms 1612 KB Output is correct
14 Correct 27 ms 1612 KB Output is correct
15 Correct 37 ms 1672 KB Output is correct
16 Correct 21 ms 1612 KB Output is correct
17 Correct 14 ms 1228 KB Output is correct
18 Correct 18 ms 1668 KB Output is correct
19 Correct 1732 ms 10144 KB Output is correct
20 Correct 1740 ms 10232 KB Output is correct
21 Correct 1676 ms 10152 KB Output is correct
22 Correct 1702 ms 10044 KB Output is correct
23 Correct 1719 ms 10080 KB Output is correct
24 Correct 867 ms 27112 KB Output is correct
25 Correct 793 ms 27112 KB Output is correct
26 Correct 770 ms 27028 KB Output is correct
27 Correct 797 ms 27184 KB Output is correct
28 Correct 723 ms 27076 KB Output is correct
29 Correct 667 ms 27108 KB Output is correct
30 Correct 646 ms 26992 KB Output is correct
31 Correct 579 ms 27140 KB Output is correct
32 Correct 211 ms 560 KB Output is correct
33 Correct 645 ms 26996 KB Output is correct
34 Correct 1848 ms 54692 KB Output is correct
35 Correct 1892 ms 54620 KB Output is correct
36 Correct 1615 ms 54700 KB Output is correct
37 Correct 1666 ms 54668 KB Output is correct
38 Correct 1634 ms 54620 KB Output is correct
39 Correct 1494 ms 54620 KB Output is correct
40 Correct 1647 ms 54624 KB Output is correct
41 Correct 1699 ms 54616 KB Output is correct
42 Correct 1685 ms 54588 KB Output is correct
43 Correct 1652 ms 54692 KB Output is correct
44 Correct 1623 ms 54644 KB Output is correct
45 Correct 1598 ms 54620 KB Output is correct
46 Correct 1731 ms 54632 KB Output is correct
47 Correct 1670 ms 54640 KB Output is correct
48 Correct 1772 ms 54716 KB Output is correct
49 Correct 1451 ms 54620 KB Output is correct
50 Correct 1390 ms 54616 KB Output is correct
51 Correct 1411 ms 54708 KB Output is correct
52 Correct 1399 ms 54584 KB Output is correct
53 Correct 1366 ms 54748 KB Output is correct
54 Correct 1338 ms 54708 KB Output is correct
55 Correct 965 ms 33536 KB Output is correct
56 Correct 1337 ms 54660 KB Output is correct
57 Incorrect 1782 ms 15628 KB Output isn't correct
58 Halted 0 ms 0 KB -