Submission #1107568

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107568		the_ZHER	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	1072 ms	143108 KiB

sortbooks

#include <bits/stdc++.h>
#define int long long
#define boost ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define file(s) freopen(s".in", "r", stdin); freopen(s".out", "w", stdout)
const int N=1e6+1;
const int inf=1e18;
const int mod=1e9+7;
using namespace std;
struct edge{
	int l,k,id;
};
vector<edge>v1[N];
vector<int>v;
int t[4*N];
void upd(int n,int tl,int tr,int pos,int x){
	if(tl==tr){
		t[n]=x;
		return;
	}
	int mid=(tl+tr)/2;
	if(pos<=mid){
		upd(n*2,tl,mid,pos,x);
	}else{
		upd(n*2+1,mid+1,tr,pos,x);
	}
	t[n]=max(t[n*2],t[n*2+1]);
}
int get(int n,int tl,int tr,int l,int r){
	if(tr<l||r<tl){
		return 0;
	}
	if(l<=tl&&tr<=r){
		return t[n];
	}
	int mid=(tl+tr)/2;
	return max(get(n*2,tl,mid,l,r),get(n*2+1,mid+1,tr,l,r));
}
stack<int >st;
int pos[N];
int ans[N];
signed main(){
	boost;
	int n,m;
	cin>>n>>m;
	v.push_back(0);
	for(int i=1;i<=n;i++){
		int x;
		cin>>x;
		v.push_back(x);
	}
	for(int i=1;i<=n;i++){
		while(st.size()>0&&v[st.top()]<=v[i]){
			st.pop();
		}
		if(st.size()>0){
			pos[i]=st.top();
		}
		st.push(i);
	}
	for(int i=1;i<=m;i++){
		int l,r,k;
		cin>>l>>r>>k;
		edge x;
		x.l=l;
		x.k=k;
		x.id=i;
		v1[r].push_back(x);
	}
	for(int i=1;i<=n;i++){
		if(pos[i]>0){
			int y=v[pos[i]];
			upd(1,1,n,pos[i],y+v[i]);
		}
	for(int j=0;j<v1[i].size();j++){
		ans[v1[i][j].id]=(get(1,1,n,v1[i][j].l,i)<=v1[i][j].k);
	}	
	st.push(i);
	}
	for(int i=1;i<=m;i++){
		cout<<ans[i]<<"\n";
	}
}

Compilation message (stderr)

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:74:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |  for(int j=0;j<v1[i].size();j++){
      |              ~^~~~~~~~~~~~~

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