Submission #482778

#	Time	Username	Problem	Language	Result	Execution time	Memory
482778		luka1234	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	100 / 100	2742 ms	107336 KiB

sortbooks

#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
using namespace std;
int t[4000001];
int n,m;
int a[1000001];	
stack<int> st;
int ans[1000001];
vector<pair<pair<int,int>,pair<int,int> > >vec1;
int get(int v,int tl,int tr,int l,int r){
	if(l==tl&&r==tr){
		return t[v];
	}
	int m=(tl+tr)/2;
	if(r<=m)
	   return get(2*v,tl,m,l,r);
	else{
		if(l>m)
		   return get(2*v+1,m+1,tr,l,r);
		else
		   return max(get(2*v,tl,m,l,m),get(2*v+1,m+1,tr,m+1,r));
	}
}
void update(int v,int tl,int tr,int x,int p){
	if(tl==tr){
		t[v]=x;
	}
	else{
		int m=(tl+tr)/2;
		if(p<=m)
		   update(2*v,tl,m,x,p);
		else 
		   update(2*v+1,m+1,tr,x,p);
		   
		t[v]=max(t[2*v],t[2*v+1]);
	}
}
int main(){
	cin>>n>>m;
	for(int k=1;k<=n;k++){
		cin>>a[k];
	}
	vector<vector<int> > vec(n+1);
    for(int i=1;i<=n;i++){
        while(!st.empty()){
            int v=st.top();
            if(a[v]<=a[i])
			   st.pop();
            else 
			   break;
        }
        if(!st.empty()){
            int x=st.top();
            vec[x].push_back(i);
        }
        st.push(i);
    }
    
    for(int i=1;i<=m;i++){
        int l,r,x;
		cin>>l>>r>>x;
        vec1.push_back({{-l,r},{x,i}});
    }
    sort(vec1.begin(),vec1.end());
    int ind=0;
    for(int k=n;k>=1;k--){
        for(int pos:vec[k]){
            update(1,1,n,a[pos]+a[k],pos);
        }
        while(ind<m){
            int l=-vec1[ind].ff.ff;
            if(l!=k)
			   break;
            int r=vec1[ind].ff.ss;
            int pir=vec1[ind].ss.ff;
            int meo=vec1[ind].ss.ss;
            int x=get(1,1,n,l,r);
            if(x>pir)
			   ans[meo]=0;
            else 
			   ans[meo]=1;
            ind++;
        }
    }
    for(int k=1;k<=m;k++){
        cout<<ans[k]<<"\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