Submission #166351

#	Time	Username	Problem	Language	Result	Execution time	Memory
166351		koste4ka	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	64 / 100	3027 ms	110264 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 ans[N];

set < int > all[N];

int a[N];

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 block = 2000;
    int n, m;
    cin >> n >> m;
    int ind;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        ind = i / block;
        if (!all[ind].empty() && a[i] < *all[ind].rbegin()) {
            ans[ind] = max(ans[ind], a[i] + *all[ind].rbegin());
        }
        all[ind].insert(a[i]);
    }
    int l, r, k;
    int res;
    int best;
    while (m--) {
        cin >> l >> r >> k;
        --l;
        --r;
        res = 0;
        best = 0;
        for (int i = l; i <= r;) {
            if (i % block == 0 && i + block - 1 <= r) {
                res = max(res, ans[i / block]);
                if (best > *all[i / block].begin()) {
                    auto it = all[i / block].lower_bound(best);
                    --it;
                    res = max(res, best + *it);
                }
                best = max(best, *all[i / block].rbegin());
                i += block;
            } else {
                if (best > a[i]) {
                    res = max(res, best + a[i]);
                }
                best = max(best, a[i]);
                ++i;
            }
        }
        cout << (res <= k) << '\n';
    }
    return 0;
}

Compilation message (stderr)

sortbooks.cpp:45: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