oj.uz

Submission #168446

# Submission time Handle Problem Language Result Execution time Memory
168446 2019-12-13T06:21:47 Z koste4ka Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
64 / 100
 1960 ms 262144 KB 
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-O3")

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>

#define pb push_back
#define F first
#define S second
#define lll unsigned long long
#define lld long double

#define data sdadsd

//#define int lll

using namespace std;
using namespace __gnu_pbds;

template <typename T>
using ordered_set = tree <T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

mt19937 gen(chrono::system_clock::now().time_since_epoch().count());

const int N = 1e6 + 229;
const lll M = 1e9 + 7;
const lll M2 = 1e9 + 9;
const lll mod = 998244353;
const int rx[4] = {0, 0, -1, 1};
const int ry[4] = {-1, 1, 0, 0};
const lld eps = 1e-11;
const double pi = acos(-1.0);

int a[N];

int n;

vector < set < int > > all;

vector < int > ans;

vector < int > need;

void prec(int v, int l, int r) {
    for (int i = l; i < min(r, n); ++i) {
        if (i > l && a[i] < *all[v].rbegin()) {
            ans[v] = max(ans[v], a[i] + *all[v].rbegin());
        }
        all[v].insert(a[i]);
    }
    if (l + 1 == r) {
        return;
    }
    int mid = (l + r) / 2;
    prec(v * 2, l, mid);
    prec(v * 2 + 1, mid, r);
}

void go(int v, int l, int r, int cl, int cr) {
    if (cl >= r || cr <= l) {
        return;
    }
    if (cl >= l && cr <= r) {
        need.pb(v);
        return;
    }
    int mid = (cl + cr) / 2;
    go(v * 2, l, r, cl, mid);
    go(v * 2 + 1, l, r, mid, cr);
}

main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    srand(time(0));
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
//    freopen("maxxor.in", "r", stdin);
//    freopen("maxxor.out", "w", stdout);
#endif
    int m;
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    int st = 0;
    while ((1 << st) < n) {
        ++st;
    }
    ans.resize(1 << (st + 1));
    all.resize(1 << (st + 1));
    prec(1, 0, 1 << st);
    int l, r, k;
    int res;
    int best;
    while (m--) {
        cin >> l >> r >> k;
        --l;
        need.clear();
        go(1, l, r, 0, 1 << st);
        res = 0;
        best = 0;
        for (auto i : need) {
            if (best > *all[i].begin()) {
                auto it = all[i].lower_bound(best);
                --it;
                res = max(res, best + *it);
            }
            best = max(best, *all[i].rbegin());
            res = max(res, ans[i]);
        }
        cout << (res <= k) << '\n';
    }
    return 0;
}

Compilation message

sortbooks.cpp:77:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 508 KB Output is correct
6 Correct 3 ms 632 KB Output is correct
7 Correct 3 ms 632 KB Output is correct
8 Correct 3 ms 632 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 2 ms 504 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 508 KB Output is correct
6 Correct 3 ms 632 KB Output is correct
7 Correct 3 ms 632 KB Output is correct
8 Correct 3 ms 632 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 2 ms 504 KB Output is correct
11 Correct 8 ms 1500 KB Output is correct
12 Correct 19 ms 4508 KB Output is correct
13 Correct 19 ms 4472 KB Output is correct
14 Correct 23 ms 4728 KB Output is correct
15 Correct 22 ms 4728 KB Output is correct
16 Correct 17 ms 4600 KB Output is correct
17 Correct 12 ms 3448 KB Output is correct
18 Correct 8 ms 1784 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 1831 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 592 ms 67192 KB Output is correct
2 Correct 514 ms 67320 KB Output is correct
3 Correct 192 ms 25104 KB Output is correct
4 Correct 187 ms 25084 KB Output is correct
5 Correct 186 ms 25064 KB Output is correct
6 Correct 145 ms 25172 KB Output is correct
7 Correct 145 ms 25048 KB Output is correct
8 Correct 160 ms 24312 KB Output is correct
9 Correct 53 ms 1656 KB Output is correct
10 Correct 162 ms 24696 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 508 KB Output is correct
6 Correct 3 ms 632 KB Output is correct
7 Correct 3 ms 632 KB Output is correct
8 Correct 3 ms 632 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 2 ms 504 KB Output is correct
11 Correct 8 ms 1500 KB Output is correct
12 Correct 19 ms 4508 KB Output is correct
13 Correct 19 ms 4472 KB Output is correct
14 Correct 23 ms 4728 KB Output is correct
15 Correct 22 ms 4728 KB Output is correct
16 Correct 17 ms 4600 KB Output is correct
17 Correct 12 ms 3448 KB Output is correct
18 Correct 8 ms 1784 KB Output is correct
19 Correct 1960 ms 210204 KB Output is correct
20 Correct 1914 ms 209196 KB Output is correct
21 Correct 1637 ms 211276 KB Output is correct
22 Correct 1616 ms 210744 KB Output is correct
23 Correct 1610 ms 211320 KB Output is correct
24 Correct 906 ms 210808 KB Output is correct
25 Correct 919 ms 210760 KB Output is correct
26 Correct 1018 ms 211116 KB Output is correct
27 Correct 994 ms 210944 KB Output is correct
28 Correct 1012 ms 211020 KB Output is correct
29 Correct 1016 ms 212092 KB Output is correct
30 Correct 1029 ms 213368 KB Output is correct
31 Correct 1026 ms 213396 KB Output is correct
32 Correct 1020 ms 213496 KB Output is correct
33 Correct 1028 ms 213368 KB Output is correct
34 Correct 886 ms 212984 KB Output is correct
35 Correct 877 ms 213140 KB Output is correct
36 Correct 876 ms 212736 KB Output is correct
37 Correct 876 ms 212856 KB Output is correct
38 Correct 879 ms 212984 KB Output is correct
39 Correct 1124 ms 211952 KB Output is correct
40 Correct 648 ms 129912 KB Output is correct
41 Correct 349 ms 51724 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 508 KB Output is correct
6 Correct 3 ms 632 KB Output is correct
7 Correct 3 ms 632 KB Output is correct
8 Correct 3 ms 632 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 2 ms 504 KB Output is correct
11 Correct 8 ms 1500 KB Output is correct
12 Correct 19 ms 4508 KB Output is correct
13 Correct 19 ms 4472 KB Output is correct
14 Correct 23 ms 4728 KB Output is correct
15 Correct 22 ms 4728 KB Output is correct
16 Correct 17 ms 4600 KB Output is correct
17 Correct 12 ms 3448 KB Output is correct
18 Correct 8 ms 1784 KB Output is correct
19 Runtime error 1831 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -