Submission #964907

#	Time	Username	Problem	Language	Result	Execution time	Memory
964907		Acanikolic	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	100 / 100	1288 ms	110256 KiB

sortbooks

#include <bits/stdc++.h>
		 		
//#define int long long 
		 
#define pb push_back 
		
#define F first
		 
#define S second
		 
using namespace std;
		 
const int N = 1000000 + 10;
		 
const int mod = 1e9 + 7;
		 
const int inf = 1e9; 	

int a[N],res[N];
vector<array<int,3>>kveri[N];

long long st[N * 4];

void update(int node,int tl,int tr,int index,long long val) {
	if(tl > index || tr < index) return;
	if(tl == tr) {
		st[node] = val;
		return;
	}
	int mid = (tl + tr) / 2;
	update(node * 2,tl,mid,index,val);
	update(node * 2 + 1,mid + 1,tr,index,val);
	st[node] = max(st[node * 2],st[node * 2 + 1]);
}

long long get(int node,int tl,int tr,int l,int r) {
	if(tl > r || tr < l) return 0ll;
	if(tl >= l && tr <= r) return st[node];
	int mid = (tl + tr) / 2;
	return max(get(node * 2,tl,mid,l,r),get(node * 2 + 1,mid + 1,tr,l,r));
}
	 		 
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
	
	int n,q;
	cin >> n >> q;
	vector<int>a(n + 1);
	for(int i = 1; i <= n; i++) cin >> a[i];
	vector<int>prev(n + 1,-1);
	stack<int>st;
	for(int i = 1; i <= n; i++) {
		while(st.size() && a[st.top()] <= a[i]) st.pop();
		if(st.size()) prev[i] = st.top();
		st.push(i);
	}
	for(int i = 1; i <= q; i++) {
		int l,r,k;
		cin >> l >> r >> k;
		kveri[r].pb({l,k,i});
	}
	for(int i = 1; i <= n; i++) {
		if(prev[i] != -1) update(1,1,n,prev[i],a[prev[i]] + a[i]);
		for(auto X : kveri[i]) {
			res[X[2]] = (get(1,1,n,X[0],i) > X[1] ? 0 : 1);
		}
	}
	for(int i = 1; i <= q; i++) cout << res[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