Submission #168453

#	Time	Username	Problem	Language	Result	Execution time	Memory
168453		koste4ka	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	64 / 100	3054 ms	258384 KiB

sortbooks

//#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, m;

vector < vector < int > > all;

vector < int > ans;

vector < int > need[N];

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[m].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
    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;
        go(1, l, r, 0, 1 << st);
        res = 0;
        best = 0;
        for (auto i : need[m]) {
            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 (stderr)

sortbooks.cpp:81:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 0 / 13
• Subtask 4: 17 / 17
• Subtask 5: 30 / 30
• Subtask 6: 0 / 23