oj.uz

Submission #166362

# Submission time Handle Problem Language Result Execution time Memory
166362 2019-12-01T19:10:28 Z koste4ka Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
64 / 100
 2252 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 = 4e6 + 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 n;

vector < set < int > > all;

vector < int > ans;

vector < int > need;

int st;

void prec(int v, int l, int r) {
    for (int i = l; i < min(r, n); ++i) {
        if (i > l && *all[(1 << st) + i].begin() < *all[v].rbegin()) {
            ans[v] = max(ans[v], *all[(1 << st) + i].begin() + *all[v].rbegin());
        }
        all[v].insert(*all[(1 << st) + i].begin());
    }
    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;
    while ((1 << st) < n) {
        ++st;
    }
    all.resize(1 << (st + 1));
    ans.resize(1 << (st + 1));
    int x;
    for (int i = 0; i < n; ++i) {
        cin >> x;
        all[(1 << st) + i].insert(x);
    }
    prec(1, 0, 1 << st);
    int l, r, k;
    int res;
    int best;
    while (m--) {
        cin >> l >> r >> k;
        --l;
        need.clear();
        need.shrink_to_fit();
        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 3 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 632 KB Output is correct
7 Correct 5 ms 632 KB Output is correct
8 Correct 3 ms 632 KB Output is correct
9 Correct 3 ms 508 KB Output is correct
10 Correct 3 ms 376 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 3 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 632 KB Output is correct
7 Correct 5 ms 632 KB Output is correct
8 Correct 3 ms 632 KB Output is correct
9 Correct 3 ms 508 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 9 ms 1400 KB Output is correct
12 Correct 54 ms 4344 KB Output is correct
13 Correct 21 ms 4344 KB Output is correct
14 Correct 25 ms 4472 KB Output is correct
15 Correct 25 ms 4532 KB Output is correct
16 Correct 19 ms 4524 KB Output is correct
17 Correct 13 ms 3320 KB Output is correct
18 Correct 9 ms 1656 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 2055 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 858 ms 66676 KB Output is correct
2 Correct 604 ms 66884 KB Output is correct
3 Correct 248 ms 24840 KB Output is correct
4 Correct 252 ms 24904 KB Output is correct
5 Correct 239 ms 24972 KB Output is correct
6 Correct 184 ms 24952 KB Output is correct
7 Correct 186 ms 24948 KB Output is correct
8 Correct 198 ms 24020 KB Output is correct
9 Correct 79 ms 1468 KB Output is correct
10 Correct 202 ms 23992 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 3 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 632 KB Output is correct
7 Correct 5 ms 632 KB Output is correct
8 Correct 3 ms 632 KB Output is correct
9 Correct 3 ms 508 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 9 ms 1400 KB Output is correct
12 Correct 54 ms 4344 KB Output is correct
13 Correct 21 ms 4344 KB Output is correct
14 Correct 25 ms 4472 KB Output is correct
15 Correct 25 ms 4532 KB Output is correct
16 Correct 19 ms 4524 KB Output is correct
17 Correct 13 ms 3320 KB Output is correct
18 Correct 9 ms 1656 KB Output is correct
19 Correct 2068 ms 207280 KB Output is correct
20 Correct 2252 ms 207624 KB Output is correct
21 Correct 1834 ms 207424 KB Output is correct
22 Correct 1836 ms 207576 KB Output is correct
23 Correct 1809 ms 207396 KB Output is correct
24 Correct 1027 ms 207608 KB Output is correct
25 Correct 1018 ms 207480 KB Output is correct
26 Correct 1101 ms 207408 KB Output is correct
27 Correct 1146 ms 208332 KB Output is correct
28 Correct 1136 ms 208300 KB Output is correct
29 Correct 1126 ms 208340 KB Output is correct
30 Correct 1149 ms 208464 KB Output is correct
31 Correct 1125 ms 208456 KB Output is correct
32 Correct 1158 ms 208376 KB Output is correct
33 Correct 1133 ms 208476 KB Output is correct
34 Correct 978 ms 208592 KB Output is correct
35 Correct 1002 ms 208580 KB Output is correct
36 Correct 960 ms 208584 KB Output is correct
37 Correct 985 ms 208560 KB Output is correct
38 Correct 967 ms 208520 KB Output is correct
39 Correct 1272 ms 208844 KB Output is correct
40 Correct 713 ms 127716 KB Output is correct
41 Correct 445 ms 49036 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 3 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 632 KB Output is correct
7 Correct 5 ms 632 KB Output is correct
8 Correct 3 ms 632 KB Output is correct
9 Correct 3 ms 508 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 9 ms 1400 KB Output is correct
12 Correct 54 ms 4344 KB Output is correct
13 Correct 21 ms 4344 KB Output is correct
14 Correct 25 ms 4472 KB Output is correct
15 Correct 25 ms 4532 KB Output is correct
16 Correct 19 ms 4524 KB Output is correct
17 Correct 13 ms 3320 KB Output is correct
18 Correct 9 ms 1656 KB Output is correct
19 Runtime error 2055 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -