Submission #1259827

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259827		Dreamy_lovesper	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	100 / 100	503 ms	101980 KiB

sortbooks

#include <bits/stdc++.h>

using namespace std;

// Do you think you'll ever remember me someday, or will I just fade away from your memory?
#define LIFESUCK ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long
#define str string
#define mll map<ll, ll>
#define vll vector<ll>
#define pll pair<ll, ll>
#define pii pair<int, int>
#define fi first
#define se second
#define all(c) c.begin(), c.end()
#define pb push_back
#define mpp make_pair
#define sz(s) (int)s.size()
#define debug cout << "I Love You\n";
#define fu(i, a, b) for (ll i = a; i <= b; i++)
#define fd(i, b, a) for (ll i = b; i >= a; i--)
#define Bitc(msk, j) ((msk >> j) & 1)
#define _log(x) 31 - __builtin_clz(x)
#define LoveTime chrono::steady_clock::now().time_since_epoch().count()

const ll Mod = 998244353;
const ll inf = (1ll << 30);
const ll lnf = (1ll << 60);

// When time passes and things change... will you still remember someone like me?
int64_t add(ll &a, ll b) {
    a += b;
    if (a >= Mod) a %= Mod;
    while (a < 0) a += Mod;
    return a;
}
int64_t mul(ll a, ll b) {
    a = 1ll * a * b % Mod;
    return a;
}

template <class X, class Y>
bool minimize(X &x, Y y) {
    X eps = 1e-9;
    if (x > y + eps) {
        x = y;
        return 1;
    }
    return 0;
}

template <class X, class Y>
bool maximize(X &x, Y y) {
    X eps = 1e-9;
    if (x + eps < y) {
        x = y;
        return 1;
    }
    return 0;
}

// I wonder… will I just become a distant memory to you one day?
#define mxn 1'000'007
ll n, q, g[mxn], f[mxn];
ll ans[mxn];

struct Quest {
    ll l, k, id;
};

vector<Quest> Qu[mxn];

struct Fenwick {
    ll n;
    vll fen;
    Fenwick(ll _n): n(_n), fen(_n + 7, 0) {}

    void update(ll id, ll val) {
        for(; id; id -= id & -id) maximize(fen[id], val);
    }

    ll get(ll id) {
        ll sad = -lnf;
        for(; id <= n; id += id & -id) maximize(sad, fen[id]);
        return sad;
    }
};

// The world is still beautiful, only it’s a pity that you are no longer among the living.
void lovesper(const ll &TestCase) {
    cin >> n >> q;
    fu(i, 1, n) cin >> g[i];

    fu(i, 1, q) {
        ll l, r, k; cin >> l >> r >> k;
        Qu[r].pb({l, k, i});
    }

    Fenwick fen(n);
    stack<ll> st;
    
    fu(i, 1, n) {
        while(!st.empty() && g[st.top()] <= g[i]) st.pop();
        if(!st.empty()) fen.update(st.top(), g[st.top()] + g[i]);
        for(auto&[l, k, id]: Qu[i]) ans[id] = (fen.get(l) <= k);
        st.push(i);
    }

    fu(i, 1, q) cout << ans[i] << '\n';
}


//    In the future, each of us will have our own path..
// ...But no matter where we go, we will always be a beautiful part of each other’s memories.
signed main() {
    LIFESUCK

    #define name "lovesper"
    // freopen(name".inp", "r", stdin);
    // freopen(name".out", "w", stdout);

    ll Test = 1;
    // cin >> Test;

    fu(i, 1, Test) {
        lovesper(i);
        if (i < Test) cout << '\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