Submission #837936

#	Time	Username	Problem	Language	Result	Execution time	Memory
837936		MODDI	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	100 / 100	2694 ms	104780 KiB

sortbooks

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<long long, long long> pll;
typedef pair<int,int> pii;
typedef vector<long long> vl;
typedef vector<int> vi;
int n, m;
vi arr;
const int MXN = 1e6+5;
vector<array<int, 3>> queries[MXN];
bool comp(array<int, 3>& a, array<int, 3>& b){
	return a[0] < b[0];
}
int tree[4 * MXN], lazy[4 * MXN];
void push(int node, int l, int r){
	if(lazy[node] == 0)	return;
	tree[node] = max(tree[node], lazy[node]);
	if(l != r){
		lazy[node*2] = max(lazy[node*2], lazy[node]);
		lazy[node*2+1] = max(lazy[node*2+1], lazy[node]);
	}
	lazy[node] = 0;
}
void update(int node, int l, int r, int L, int R, int val){
	push(node, l, r);
	if(r < L || l > R)	return;
	if(L <= l && r <= R){
		lazy[node] = max(lazy[node], val);
		push(node, l, r);
		return;
	}
	int mid = (l + r) / 2;
	update(node*2, l, mid, L, R, val);
	update(node*2+1, mid+1, r, L, R, val);
	tree[node] = max(tree[node*2], tree[node*2+1]);
}
int query(int node, int l, int r, int L, int R){
	push(node, l, r);
	if(r < L || l > R)	return 0;
	if(L <= l && r <= R)	return tree[node];
	int mid = (l + r) / 2;
	return max(query(node*2, l, mid, L, R), query(node*2+1, mid+1, r, L, R));
}
int main(){
	cin>>n>>m;
	arr.resize(n);
	for(int i = 0; i < n; i++)	cin>>arr[i];
	
	vi ans(m);
	for(int i = 0; i < m; i++){
		int l, r, k;
		cin>>l>>r>>k;
		l--;
		r--;
		queries[r].pb({l, k, i});
	}
	stack<int> store;
	for(int i = 0; i < n; i++){
		while(!store.empty() && arr[store.top()] <= arr[i])
			store.pop();
		if(!store.empty()){
			update(1, 0, n-1, 1, store.top(), arr[i] + arr[store.top()]);
		}
		for(auto t : queries[i]){
			int l = t[0];
			int k = t[1];
			int id = t[2];
			if(query(1, 0, n-1, l, i) <= k)
				ans[id] = 1;
			else
				ans[id] = 0;
		}
		store.push(i);
	}
	for(auto t : ans)
		cout<<t<<"\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