oj.uz

Submission #166355

# Submission time Handle Problem Language Result Execution time Memory
166355 2019-12-01T18:49:07 Z koste4ka Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
17 / 100
 682 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 = 5e6 + 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 218 ms 235404 KB Output is correct
2 Correct 219 ms 235236 KB Output is correct
3 Correct 222 ms 235316 KB Output is correct
4 Correct 217 ms 235276 KB Output is correct
5 Correct 219 ms 235384 KB Output is correct
6 Correct 217 ms 235512 KB Output is correct
7 Correct 219 ms 235484 KB Output is correct
8 Correct 252 ms 235512 KB Output is correct
9 Correct 219 ms 235384 KB Output is correct
10 Correct 219 ms 235256 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 235404 KB Output is correct
2 Correct 219 ms 235236 KB Output is correct
3 Correct 222 ms 235316 KB Output is correct
4 Correct 217 ms 235276 KB Output is correct
5 Correct 219 ms 235384 KB Output is correct
6 Correct 217 ms 235512 KB Output is correct
7 Correct 219 ms 235484 KB Output is correct
8 Correct 252 ms 235512 KB Output is correct
9 Correct 219 ms 235384 KB Output is correct
10 Correct 219 ms 235256 KB Output is correct
11 Correct 235 ms 236132 KB Output is correct
12 Correct 232 ms 238556 KB Output is correct
13 Correct 234 ms 238552 KB Output is correct
14 Correct 246 ms 238848 KB Output is correct
15 Correct 267 ms 238888 KB Output is correct
16 Correct 232 ms 238632 KB Output is correct
17 Correct 226 ms 237816 KB Output is correct
18 Correct 226 ms 235748 KB Output is correct

Subtask #3
0 / 13.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 235404 KB Output is correct
2 Correct 219 ms 235236 KB Output is correct
3 Correct 222 ms 235316 KB Output is correct
4 Correct 217 ms 235276 KB Output is correct
5 Correct 219 ms 235384 KB Output is correct
6 Correct 217 ms 235512 KB Output is correct
7 Correct 219 ms 235484 KB Output is correct
8 Correct 252 ms 235512 KB Output is correct
9 Correct 219 ms 235384 KB Output is correct
10 Correct 219 ms 235256 KB Output is correct
11 Correct 235 ms 236132 KB Output is correct
12 Correct 232 ms 238556 KB Output is correct
13 Correct 234 ms 238552 KB Output is correct
14 Correct 246 ms 238848 KB Output is correct
15 Correct 267 ms 238888 KB Output is correct
16 Correct 232 ms 238632 KB Output is correct
17 Correct 226 ms 237816 KB Output is correct
18 Correct 226 ms 235748 KB Output is correct
19 Runtime error 429 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 218 ms 235404 KB Output is correct
2 Correct 219 ms 235236 KB Output is correct
3 Correct 222 ms 235316 KB Output is correct
4 Correct 217 ms 235276 KB Output is correct
5 Correct 219 ms 235384 KB Output is correct
6 Correct 217 ms 235512 KB Output is correct
7 Correct 219 ms 235484 KB Output is correct
8 Correct 252 ms 235512 KB Output is correct
9 Correct 219 ms 235384 KB Output is correct
10 Correct 219 ms 235256 KB Output is correct
11 Correct 235 ms 236132 KB Output is correct
12 Correct 232 ms 238556 KB Output is correct
13 Correct 234 ms 238552 KB Output is correct
14 Correct 246 ms 238848 KB Output is correct
15 Correct 267 ms 238888 KB Output is correct
16 Correct 232 ms 238632 KB Output is correct
17 Correct 226 ms 237816 KB Output is correct
18 Correct 226 ms 235748 KB Output is correct
19 Runtime error 682 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -