Submission #382003

#	Time	Username	Problem	Language	Result	Execution time	Memory
382003		vanic	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	0 / 100	1937 ms	39000 KiB

sortbooks

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <array>

using namespace std;

const int maxn=1e6+5, Log=20, pot=(1<<Log);

struct tournament{
	int t[pot*2];
	int prop[pot*2];
	void propagate(int x){
		if(!prop[x]){
			return;
		}
		t[x]=max(t[x], prop[x]);
		if(x<pot){
			prop[x*2]=max(prop[x*2], prop[x]);
			prop[x*2+1]=max(prop[x*2+1], prop[x]);
		}
		prop[x]=0;
		
	}
	void update(int x, int val){
		//ak waa ovo mijenjaj
		for(; x>0; x/=2){
			t[x]=max(t[x], val);
		}
	}
	void update2(int L, int D, int x, int l, int d, int val){
		propagate(x);
		if(L>=l && D<=d){
			update(x, val);
			if(x<pot){
				prop[x*2]=max(prop[x*2], val);
				prop[x*2+1]=max(prop[x*2+1], val);
			}
			return;
		}
		if((L+D)/2>=l){
			update2(L, (L+D)/2, x*2, l, d, val);
		}
		if((L+D)/2+1<=d){
			update2((L+D)/2+1, D, x*2+1, l, d, val);
		}
	}
	int query(int L, int D, int x, int l, int d){
		propagate(x);
		if(L>=l && D<=d){
			return t[x];
		}
		int lijeva=0, desna=0;
		if((L+D)/2>=l){
			lijeva=query(L, (L+D)/2, x*2, l, d);
		}
		if((L+D)/2+1<=d){
			desna=query((L+D)/2+1, D, x*2+1, l, d);
		}
		return max(lijeva, desna);
	}
};


tournament T;
int n, m;
int a[maxn];
int ind[maxn];
bool sol[maxn];
int q[maxn][3];


bool cmp(int aa, int b){
	return q[aa][1]<q[b][1];
}

vector < pair < int, int > > red;

void rijesi(){
	int pos=0;
	for(int i=0; i<n; i++){
		while(!red.empty() && red.back().first<a[i]){
			red.pop_back();
		}
		if(!red.empty()){
			T.update2(0, pot-1, 1, 0, red.back().second, red.back().first+a[i]);
		}
		red.push_back({a[i], i});
		while(pos<m && q[ind[pos]][1]==i){
			sol[ind[pos]]=T.query(0, pot-1, 1, q[ind[pos]][0], i)<=q[ind[pos]][2];
			pos++;
		}
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	for(int i=0; i<n; i++){
		cin >> a[i];
	}
	for(int i=0; i<m; i++){
		cin >> q[i][0] >> q[i][1] >> q[i][2];
		q[i][0]--;
		q[i][1]--;
		ind[i]=i;
	}
	sort(ind, ind+m, cmp);
	rijesi();
	for(int i=0; i<m; i++){
		cout << sol[i] << '\n';
	}
	return 0;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 30
• Subtask 6: 0 / 23