Submission #949156

#	Time	Username	Problem	Language	Result	Execution time	Memory
949156		atom	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	817 ms	101344 KiB

sortbooks

#include "bits/stdc++.h"
// @JASPER'S BOILERPLATE
using namespace std;
using ll = long long;

#ifdef JASPER
#include "debug.h"
#else
#define debug(...) 166
#endif

struct SegmentTree {
	vector <ll> f;
	int n;
	ll NEUTRAL = numeric_limits <ll> :: min ();
	SegmentTree(int _n) {
		n = _n;
		f.assign((n << 1) + 5, 0);
	}

	void upd(int x, ll val) {
		f[x + n] = val;
		for (x += n; x; x >>= 1)
			f[x >> 1] = max(f[x], f[x ^ 1]); 
	}

	ll qry(int l, int r) {
		ll ql = NEUTRAL, qr = NEUTRAL;
		for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
			if (l & 1) ql = max(ql, f[l++]);
			if (r & 1) qr = max(qr, f[--r]);
		}
		return max(ql, qr);
	}
};

const int N = 1e6 + 5;
using Query = tuple <int, int, int>;
vector <Query> qs[N];

int n, m;
int w[N];
bool ans[N];

signed main() {
    cin.tie(0) -> sync_with_stdio(0);
    
    #ifdef JASPER
        freopen("in1", "r", stdin);
    #endif

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> w[i];
    for (int i = 1; i <= m; ++i) {
    	int l, r, k;
    	cin >> l >> r >> k;
    	qs[r].push_back({l, k, i});
    }

    stack <int> st;
    SegmentTree seg(n);
    for (int i = 1; i <= n; ++i) {
    	while (!st.empty() && w[st.top()] <= w[i]) st.pop();
    	if (!st.empty()) {
    		seg.upd(st.top(), w[st.top()] + w[i]);
    	}
    	for (auto& [l, k, id] : qs[i]) {
    		ll mx = seg.qry(l, i); // qry(x) : maximum inversion sum of (w(l), w(r)) (l < r <= n)
    		// debug(st, w[st.top()], w[i]);
    		// debug(mx, l, i);
    		ans[id] = (mx <= k);
    	}
    	// debug(seg.qry(1, 2));
    	st.push(i);
    }
    
    for (int i = 1; i <= m; ++i)
    	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