oj.uz

Submission #166354

# Submission time Handle Problem Language Result Execution time Memory
166354 2019-12-01T18:47:51 Z koste4ka Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
64 / 100
 2097 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;

set < int > all[N];

int ans[N];

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;
    }
    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 51 ms 47352 KB Output is correct
2 Correct 46 ms 47352 KB Output is correct
3 Correct 47 ms 47352 KB Output is correct
4 Correct 47 ms 47352 KB Output is correct
5 Correct 46 ms 47384 KB Output is correct
6 Correct 47 ms 47608 KB Output is correct
7 Correct 47 ms 47608 KB Output is correct
8 Correct 47 ms 47568 KB Output is correct
9 Correct 47 ms 47480 KB Output is correct
10 Correct 47 ms 47552 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 47352 KB Output is correct
2 Correct 46 ms 47352 KB Output is correct
3 Correct 47 ms 47352 KB Output is correct
4 Correct 47 ms 47352 KB Output is correct
5 Correct 46 ms 47384 KB Output is correct
6 Correct 47 ms 47608 KB Output is correct
7 Correct 47 ms 47608 KB Output is correct
8 Correct 47 ms 47568 KB Output is correct
9 Correct 47 ms 47480 KB Output is correct
10 Correct 47 ms 47552 KB Output is correct
11 Correct 52 ms 48248 KB Output is correct
12 Correct 63 ms 50680 KB Output is correct
13 Correct 86 ms 50656 KB Output is correct
14 Correct 69 ms 50812 KB Output is correct
15 Correct 66 ms 50808 KB Output is correct
16 Correct 61 ms 50808 KB Output is correct
17 Correct 57 ms 49936 KB Output is correct
18 Correct 51 ms 47864 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 1925 ms 262144 KB Execution killed with signal 11 (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 648 ms 101232 KB Output is correct
2 Correct 564 ms 101920 KB Output is correct
3 Correct 219 ms 59384 KB Output is correct
4 Correct 227 ms 59384 KB Output is correct
5 Correct 223 ms 59540 KB Output is correct
6 Correct 175 ms 59384 KB Output is correct
7 Correct 174 ms 59384 KB Output is correct
8 Correct 191 ms 58488 KB Output is correct
9 Correct 96 ms 48760 KB Output is correct
10 Correct 185 ms 58488 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 47352 KB Output is correct
2 Correct 46 ms 47352 KB Output is correct
3 Correct 47 ms 47352 KB Output is correct
4 Correct 47 ms 47352 KB Output is correct
5 Correct 46 ms 47384 KB Output is correct
6 Correct 47 ms 47608 KB Output is correct
7 Correct 47 ms 47608 KB Output is correct
8 Correct 47 ms 47568 KB Output is correct
9 Correct 47 ms 47480 KB Output is correct
10 Correct 47 ms 47552 KB Output is correct
11 Correct 52 ms 48248 KB Output is correct
12 Correct 63 ms 50680 KB Output is correct
13 Correct 86 ms 50656 KB Output is correct
14 Correct 69 ms 50812 KB Output is correct
15 Correct 66 ms 50808 KB Output is correct
16 Correct 61 ms 50808 KB Output is correct
17 Correct 57 ms 49936 KB Output is correct
18 Correct 51 ms 47864 KB Output is correct
19 Correct 1965 ms 229072 KB Output is correct
20 Correct 2097 ms 229344 KB Output is correct
21 Correct 1655 ms 229068 KB Output is correct
22 Correct 1636 ms 229228 KB Output is correct
23 Correct 1629 ms 229212 KB Output is correct
24 Correct 953 ms 228252 KB Output is correct
25 Correct 947 ms 228316 KB Output is correct
26 Correct 1038 ms 228392 KB Output is correct
27 Correct 1077 ms 228392 KB Output is correct
28 Correct 1049 ms 228408 KB Output is correct
29 Correct 1052 ms 228260 KB Output is correct
30 Correct 1053 ms 228372 KB Output is correct
31 Correct 1130 ms 228472 KB Output is correct
32 Correct 1058 ms 228472 KB Output is correct
33 Correct 1063 ms 228216 KB Output is correct
34 Correct 970 ms 228404 KB Output is correct
35 Correct 946 ms 228500 KB Output is correct
36 Correct 917 ms 228472 KB Output is correct
37 Correct 948 ms 228472 KB Output is correct
38 Correct 911 ms 228472 KB Output is correct
39 Correct 1247 ms 228784 KB Output is correct
40 Correct 696 ms 160444 KB Output is correct
41 Correct 371 ms 68848 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 47352 KB Output is correct
2 Correct 46 ms 47352 KB Output is correct
3 Correct 47 ms 47352 KB Output is correct
4 Correct 47 ms 47352 KB Output is correct
5 Correct 46 ms 47384 KB Output is correct
6 Correct 47 ms 47608 KB Output is correct
7 Correct 47 ms 47608 KB Output is correct
8 Correct 47 ms 47568 KB Output is correct
9 Correct 47 ms 47480 KB Output is correct
10 Correct 47 ms 47552 KB Output is correct
11 Correct 52 ms 48248 KB Output is correct
12 Correct 63 ms 50680 KB Output is correct
13 Correct 86 ms 50656 KB Output is correct
14 Correct 69 ms 50812 KB Output is correct
15 Correct 66 ms 50808 KB Output is correct
16 Correct 61 ms 50808 KB Output is correct
17 Correct 57 ms 49936 KB Output is correct
18 Correct 51 ms 47864 KB Output is correct
19 Runtime error 1925 ms 262144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -