Submission #1285021

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285021		zxzuam	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	0 / 100	3101 ms	145180 KiB

sortbooks

#include <bits/stdc++.h>
//#define int long long
using ll = int64_t;
using namespace std;
constexpr int maxn = 2E5, L = 1E9;
int sz = 1;
vector <int> t(maxn * 60), lv(maxn * 60), rv(maxn * 60);
void upd(int v, int tl, int tr, int i, int x) {
    if(i < tl || tr < i) return;
    if(tl == tr){ t[v] = x; return; }
    int tm = (tl + tr) / 2;
    if(i <= tm) {
        if(!lv[v]) lv[v] = ++sz;
        upd(lv[v], tl, tm, i, x);
    }
    else {
        if(!rv[v]) rv[v] = ++sz;
        upd(rv[v], tm + 1, tr, i, x);
    }
    t[v] = max( t[lv[v]], t[rv[v]] );
}
int get(int v, int tl, int tr, int l, int r) {
    if(l > tr || tl > r) return 0;
    if(l <= tl && tr <= r) return t[v];
    int tm = (tl + tr) / 2;
    if(!lv[v]) lv[v] = ++sz;
    if(!rv[v]) rv[v] = ++sz;
    return max( get(lv[v], tl, tm, l, r), get(rv[v], tm + 1, tr, l, r));
}
void orz() {
    int n, m;
    cin >> n >> m;
    vector <int> a(n + 1);
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for(int i = 1; i <= m; i++) {
        int l, r, k;
        cin >> l >> r >> k;
        bool ok = 1;
        for(int j = l; j <= r; j++) {
            upd(1, 1, L, a[j], a[j]);
            int x = get(1, 1, L, a[j] + 1, L);
            if(x + a[j] > k) {
                ok = 0;
                break;
            }
        }
        for(int j = l; j <= r; j++) {
            upd(1, 1, L ,a[j], 0);
        }
        if(ok) {
            cout << "1\n";
        }
        else cout << "0\n";
    }
}
int32_t main() {
    ios_base::sync_with_stdio(false), cin.tie(nullptr);
    //freopen("promote.in", "r", stdin);
    //freopen("promote.out", "w", stdout);
    int T = 1;
    //cin >> T;
    while(T--) orz();
    return 0;
}

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