Submission #1292175

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292175		rayan_bd	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	2312 ms	223484 KiB

sortbooks

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

const int mxN = 1e6 + 100;

#define int long long

const int inf = 2e18 + 100;

int ar[mxN];

struct segment_tree{
	vector<int> seg, lazy;
	int N;
	void init(int n){
		seg.resize(n * 4);
		lazy.resize(n * 4, 0);
		N = n;
	}
	void push(int node, int start, int end){
		if(lazy[node] == 0) return;
		seg[node] += (end - start + 1) * lazy[node];
		if(start ^ end){
			lazy[node * 2 + 1] += lazy[node];
			lazy[node * 2 + 2] += lazy[node];
		}
		lazy[node] = 0;
	}
	void pull(int node){
		seg[node] = max(seg[node * 2 + 1], seg[node * 2 + 2]);
	}
	void update(int node, int start, int end, int l, int r, int x){
		push(node, start, end);
		if(start > r || end < l) return;
		if(start >= l && end <= r){
			lazy[node] = x;
			push(node, start, end);
			return;
		}
		int mid = start + (end - start) / 2;
		update(node * 2 + 1, start, mid, l, r, x);
		update(node * 2 + 2,  mid + 1, end, l, r, x);
		pull(node);
	}
	void update(int node, int start, int end, int idx, int v){ 
		push(node, start, end);
		if(start == end){
			seg[node] = max(seg[node], v);
			return;
		}
		int mid = start + (end - start) / 2;
		if(idx <= mid) update(node * 2 + 1, start, mid, idx, v);
		else update(node * 2 + 2, mid + 1, end, idx, v);
		pull(node);
	}
	int query(int node, int start, int end, int l, int r){
		push(node, start, end);
		if(start > r || end < l) return 0;
		if(start >= l && end <= r) return seg[node];
		int mid = start + (end - start) / 2;
		return max(query(node * 2 + 1, start, mid, l, r), query(node * 2 + 2, mid + 1, end, l, r));
	}
	int query(int l, int r){
		return query(0, 1, N, l, r);
	}
	void update(int idx, int v){
		update(0, 1, N, idx, v);
	}
	void update(int l, int r, int v){
		update(0, 1, N, l, r, v);
	}
} tr;

signed main(){

	ios_base::sync_with_stdio(0);
	cin.tie(nullptr); cout.tie(nullptr);

	int n, q;
	cin >> n >> q;

	for(int i = 1; i <= n; ++i) cin >> ar[i];

	tr.init(n + 5);

	map<int, vector<vector<int>>> mp;

	for(int i = 1, l, r, k; i <= q; ++i){
		cin >> l >> r >> k;
		mp[r].push_back({l, k, i});
	}

	stack<int> st;

	vector<int> ans(q + 5, 0);

	for(int i = 1; i <= n; ++i){
		while(st.size() && ar[st.top()] <= ar[i]){
			st.pop();
		}
		if(st.size()) tr.update(st.top(), ar[st.top()] + ar[i]);
		st.push(i);
		for(auto it : mp[i]){
			ans[it[2]] = (tr.query(it[0], i) <= it[1]);
		}
	}

	for(int i = 1; i <= q; ++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