oj.uz

Submission #168451

# Submission time Handle Problem Language Result Execution time Memory
168451 2019-12-13T06:33:12 Z koste4ka Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
64 / 100
 3000 ms 192188 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 < vector < int > > all;

vector < int > ans;

vector < int > need;

void prec(int v, int l, int r) {
    int best = 0;
    for (int i = l; i < min(r, n); ++i) {
        if (i > l && a[i] < best) {
            ans[v] = max(ans[v], a[i] + best);
        }
        all[v].pb(a[i]);
        best = max(best, a[i]);
    }
    sort(all[v].begin(), all[v].end());
    all[v].resize(unique(all[v].begin(), all[v].end()) - all[v].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;
    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;
    int it;
    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].front()) {
                it = lower_bound(all[i].begin(), all[i].end(), best) - all[i].begin();
                --it;
                res = max(res, best + all[i][it]);
            }
            best = max(best, all[i].back());
            res = max(res, ans[i]);
        }
        cout << (res <= k) << '\n';
    }
    return 0;
}

Compilation message

sortbooks.cpp:81: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 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 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 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 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 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 7 ms 760 KB Output is correct
12 Correct 10 ms 1400 KB Output is correct
13 Correct 11 ms 1400 KB Output is correct
14 Correct 13 ms 1528 KB Output is correct
15 Correct 13 ms 1528 KB Output is correct
16 Correct 10 ms 1528 KB Output is correct
17 Correct 8 ms 1144 KB Output is correct
18 Correct 9 ms 1400 KB Output is correct

Subtask #3
0 / 13.0

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

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 301 ms 20024 KB Output is correct
2 Correct 288 ms 20176 KB Output is correct
3 Correct 196 ms 20056 KB Output is correct
4 Correct 199 ms 20212 KB Output is correct
5 Correct 191 ms 19956 KB Output is correct
6 Correct 154 ms 20084 KB Output is correct
7 Correct 156 ms 20084 KB Output is correct
8 Correct 172 ms 20040 KB Output is correct
9 Correct 52 ms 764 KB Output is correct
10 Correct 171 ms 19972 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 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 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 7 ms 760 KB Output is correct
12 Correct 10 ms 1400 KB Output is correct
13 Correct 11 ms 1400 KB Output is correct
14 Correct 13 ms 1528 KB Output is correct
15 Correct 13 ms 1528 KB Output is correct
16 Correct 10 ms 1528 KB Output is correct
17 Correct 8 ms 1144 KB Output is correct
18 Correct 9 ms 1400 KB Output is correct
19 Correct 744 ms 40440 KB Output is correct
20 Correct 746 ms 40480 KB Output is correct
21 Correct 684 ms 40524 KB Output is correct
22 Correct 683 ms 40632 KB Output is correct
23 Correct 710 ms 40500 KB Output is correct
24 Correct 397 ms 40556 KB Output is correct
25 Correct 401 ms 40504 KB Output is correct
26 Correct 431 ms 40508 KB Output is correct
27 Correct 438 ms 40536 KB Output is correct
28 Correct 480 ms 40528 KB Output is correct
29 Correct 445 ms 40468 KB Output is correct
30 Correct 441 ms 40464 KB Output is correct
31 Correct 441 ms 40496 KB Output is correct
32 Correct 436 ms 40564 KB Output is correct
33 Correct 438 ms 40488 KB Output is correct
34 Correct 340 ms 40508 KB Output is correct
35 Correct 341 ms 40488 KB Output is correct
36 Correct 338 ms 40596 KB Output is correct
37 Correct 336 ms 40456 KB Output is correct
38 Correct 345 ms 40600 KB Output is correct
39 Correct 461 ms 40628 KB Output is correct
40 Correct 281 ms 24180 KB Output is correct
41 Correct 377 ms 40604 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 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 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 7 ms 760 KB Output is correct
12 Correct 10 ms 1400 KB Output is correct
13 Correct 11 ms 1400 KB Output is correct
14 Correct 13 ms 1528 KB Output is correct
15 Correct 13 ms 1528 KB Output is correct
16 Correct 10 ms 1528 KB Output is correct
17 Correct 8 ms 1144 KB Output is correct
18 Correct 9 ms 1400 KB Output is correct
19 Execution timed out 3054 ms 192188 KB Time limit exceeded
20 Halted 0 ms 0 KB -