oj.uz

Submission #166356

# Submission time Handle Problem Language Result Execution time Memory
166356 2019-12-01T18:50:05 Z koste4ka Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
34 / 100
 1972 ms 262148 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 = 2e6 + 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 90 ms 94328 KB Output is correct
2 Correct 107 ms 94484 KB Output is correct
3 Correct 100 ms 94328 KB Output is correct
4 Correct 89 ms 94328 KB Output is correct
5 Correct 90 ms 94456 KB Output is correct
6 Correct 93 ms 94588 KB Output is correct
7 Correct 92 ms 94584 KB Output is correct
8 Correct 93 ms 94584 KB Output is correct
9 Correct 91 ms 94456 KB Output is correct
10 Correct 91 ms 94328 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 94328 KB Output is correct
2 Correct 107 ms 94484 KB Output is correct
3 Correct 100 ms 94328 KB Output is correct
4 Correct 89 ms 94328 KB Output is correct
5 Correct 90 ms 94456 KB Output is correct
6 Correct 93 ms 94588 KB Output is correct
7 Correct 92 ms 94584 KB Output is correct
8 Correct 93 ms 94584 KB Output is correct
9 Correct 91 ms 94456 KB Output is correct
10 Correct 91 ms 94328 KB Output is correct
11 Correct 166 ms 95232 KB Output is correct
12 Correct 107 ms 97800 KB Output is correct
13 Correct 108 ms 97656 KB Output is correct
14 Correct 112 ms 97784 KB Output is correct
15 Correct 111 ms 97784 KB Output is correct
16 Correct 107 ms 97856 KB Output is correct
17 Correct 101 ms 96888 KB Output is correct
18 Correct 96 ms 94980 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 1972 ms 262148 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 681 ms 148756 KB Output is correct
2 Correct 621 ms 149232 KB Output is correct
3 Correct 266 ms 106616 KB Output is correct
4 Correct 268 ms 106616 KB Output is correct
5 Correct 285 ms 106780 KB Output is correct
6 Correct 227 ms 106488 KB Output is correct
7 Correct 242 ms 106488 KB Output is correct
8 Correct 237 ms 105864 KB Output is correct
9 Correct 140 ms 95864 KB Output is correct
10 Correct 235 ms 105848 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 94328 KB Output is correct
2 Correct 107 ms 94484 KB Output is correct
3 Correct 100 ms 94328 KB Output is correct
4 Correct 89 ms 94328 KB Output is correct
5 Correct 90 ms 94456 KB Output is correct
6 Correct 93 ms 94588 KB Output is correct
7 Correct 92 ms 94584 KB Output is correct
8 Correct 93 ms 94584 KB Output is correct
9 Correct 91 ms 94456 KB Output is correct
10 Correct 91 ms 94328 KB Output is correct
11 Correct 166 ms 95232 KB Output is correct
12 Correct 107 ms 97800 KB Output is correct
13 Correct 108 ms 97656 KB Output is correct
14 Correct 112 ms 97784 KB Output is correct
15 Correct 111 ms 97784 KB Output is correct
16 Correct 107 ms 97856 KB Output is correct
17 Correct 101 ms 96888 KB Output is correct
18 Correct 96 ms 94980 KB Output is correct
19 Runtime error 860 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 94328 KB Output is correct
2 Correct 107 ms 94484 KB Output is correct
3 Correct 100 ms 94328 KB Output is correct
4 Correct 89 ms 94328 KB Output is correct
5 Correct 90 ms 94456 KB Output is correct
6 Correct 93 ms 94588 KB Output is correct
7 Correct 92 ms 94584 KB Output is correct
8 Correct 93 ms 94584 KB Output is correct
9 Correct 91 ms 94456 KB Output is correct
10 Correct 91 ms 94328 KB Output is correct
11 Correct 166 ms 95232 KB Output is correct
12 Correct 107 ms 97800 KB Output is correct
13 Correct 108 ms 97656 KB Output is correct
14 Correct 112 ms 97784 KB Output is correct
15 Correct 111 ms 97784 KB Output is correct
16 Correct 107 ms 97856 KB Output is correct
17 Correct 101 ms 96888 KB Output is correct
18 Correct 96 ms 94980 KB Output is correct
19 Runtime error 1972 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -