Submission #691519

#	Time	Username	Problem	Language	Result	Execution time	Memory
691519		KiriLL1ca	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	2812 ms	116008 KiB

sortbooks

#include <bits/stdc++.h>
#define sz(x) (int)((x).size())
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define fr first
#define sc second
#define pw(x) (1ll << x)
#define bcnt(x) (__builtin_popcount(x))

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;

template <typename T> inline bool umax (T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template <typename T> inline bool umin (T &a, const T &b) { if (a > b) { a = b; return 1; } return 0; }

const int inf = 2e9 + 127;

struct seg1 {
    int n; vector <int> t;
    seg1 (int n = 0) : n(n), t(4 * n, -inf) {}
    inline void upd (int v, int tl, int tr, int pos, int x) {
        if (tl == tr) return void(t[v] = x);
        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]);
    }
    inline int getp (int v, int tl, int tr, int x) {
        if (t[v] < x) return -1;
        if (tl == tr) return tl;
        int tm = (tl + tr) >> 1;
        if (t[v << 1 | 1] > x) return getp(v << 1 | 1, tm + 1, tr, x);
        return getp(v << 1, tl, tm, x);
    }

    inline void upd (int pos, int x) { upd(1, 0, n - 1, pos, x); }
    inline int getp (int x) { return getp(1, 0, n - 1, x); }
};

struct seg2 {
    int n; vector <int> t;
    seg2 (int n = 0) : n(n), t(4 * n) {}
    inline void upd (int v, int tl, int tr, int pos, int x) {
        if (tl == tr) return void(umax(t[v], x));
        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]);
    }
    inline int get (int v, int tl, int tr, int l, int r) {
        if (tl > r || l > tr) return 0;
        if (l <= tl && tr <= r) return t[v];
        int tm = (tl + tr) >> 1;
        return max(get(v << 1, tl, tm, l, r), get(v << 1 | 1, tm + 1, tr, l, r));
    }

    inline void upd (int pos, int x) { upd(1, 0, n - 1, pos, x); }
    inline int get (int l, int r) { return get(1, 0, n - 1, l, r); }
};

inline void solve () {
    int n, q; cin >> n >> q;
    vector <int> a (n);
    for (auto &i : a) cin >> i;
    vector <vector <array <int, 3>>> qry (n);
    for (int i = 0; i < q; ++i) {
        int l, r, w; cin >> l >> r >> w; --l, --r;
        qry[r].pb({l, w, i});
    }

    seg1 mx (n);
    seg2 answ (n);

    vector <bool> ans (q);
    for (int r = 0; r < n; ++r) {
        int pos = mx.getp(a[r]);
        mx.upd(r, a[r]);
        if (~pos) answ.upd(pos, a[pos] + a[r]);
        for (auto [l, w, i] : qry[r]) ans[i] = (answ.get(l, r) <= w);
    }

    for (auto i : ans) cout << i << endl;
}

signed main ()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif // LOCAL

    int t = 1; // cin >> t;
    while (t--) solve();
    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