Submission #502590

#	Time	Username	Problem	Language	Result	Execution time	Memory
502590		stanislavpolyn	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	1205 ms	65116 KiB

sortbooks

#include <bits/stdc++.h>

#define fr(i, a, b) for(int i = (a); i <= (b); ++i)
#define rf(i, a, b) for(int i = (a); i >= (b); --i)
#define fe(x, y) for(auto& x : y)

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define mt make_tuple

#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define pw(x) (1LL << (x))

using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define fbo find_by_order
#define ook order_of_key

template<typename T>
bool umn(T& a, T b) { return (a > b ? (a = b, 1) : 0); }
template<typename T>
bool umx(T& a, T b) { return (a < b ? (a = b, 1) : 0); }

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template<typename T>
using ve = vector<T>;

const int N = 1e6 + 5;

int n, m;
int a[N];
int nxt[N], prv[N];
ve<array<int, 4>> Q;
int ans[N];

int t[4 * N];

void build(int v, int tl, int tr) {
    t[v] = 1e9;
    if(tl == tr) {
        return;
    }
    int tm = (tl + tr) >> 1;
    build(v << 1, tl, tm);
    build(v << 1 | 1, tm + 1, tr);
}

void upd(int v, int tl, int tr, int pos, int x) {
    if(tl == tr) {
        umx(t[v], x);
        return;
    }
    int tm = (tl + tr) >> 1;
    if(pos <= tm) {
        upd(v << 1, tl, tm, pos, x);
    } else {
        upd(v << 1 | 1, tm + 1, tr, pos, x);
    }
    t[v] = max(t[v << 1], t[v << 1 | 1]);
}

void upd(int pos, int x) {
    upd(1, 1, n, pos, x);
}

int get(int v, int tl, int tr, int l, int r) {
    if(l > r) return -1e9;
    if(tl == l && tr == r) {
        return t[v];
    }
    int tm = (tl + tr) >> 1;
    return max(get(v << 1, tl, tm, l, min(r, tm)), get(v << 1 | 1, tm + 1, tr, max(tm + 1, l), r));
}

int get(int l, int r) {
    return get(1, 1, n, l, r);
}

int main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
#else
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
#endif

    cin >> n >> m;

    fr(i, 1, n) cin >> a[i];

    fr(i, 1, n) {
        nxt[i] = -1;
        prv[i] = -1;
    }

    ve<pii> st;
    rf(i, n, 1) {
        while(sz(st) && st.back().fi < a[i]) {
            prv[st.back().se] = i;
            st.pop_back();
        }
        st.pb({a[i], i});
    }

    fr(i, 1, m) {
        int l, r, k;
        cin >> l >> r >> k;
        Q.pb(array<int, 4>{l, r, k, i});
    }

    sort(all(Q), [](array<int, 4> a, array<int, 4> b) {
        return a[1] < b[1];
    });

    int ptr = 0;
    fr(i, 1, n) {
        if(prv[i] != -1) {
            upd(prv[i], a[i] + a[prv[i]]);
        }

        while(ptr < sz(Q) && Q[ptr][1] == i) {
            ans[Q[ptr][3]] = get(Q[ptr][0], i) > Q[ptr][2] ? 0 : 1;
            ptr++;
        }
    }

    fr(i, 1, m) {
        cout << ans[i] << "\n";
    }

    return 0;
}

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