Submission #652133

#	Time	Username	Problem	Language	Result	Execution time	Memory
652133		peter940324	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	1137 ms	77972 KiB

sortbooks

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define double long double
#define IO ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

#define pii pair<int,int>
#define ff first
#define ss second
#define mp make_pair

#define pb push_back
#define pf push_front
#define all(x) x.begin(),x.end()

#define de(x) cout << #x << ' ' << x << '\n';
template<class T> void prt(T l,T r){
  while(l!=r) cout << *l << ' ',l++;
  cout << '\n';
}

const int N=1e6+5,M=1e9+7,INF=1e18;

struct qr{
	int l,r,k,i,ans;
};

struct SegTree{
	int a[4*N]{0};
	void mod(int l,int r,int cur,int ind,int val){
		if(r-l<=1){
			a[cur]=val;
			return;
		}
		int mid=(l+r)/2;
		if(ind<mid) mod(l,mid,cur*2,ind,val);
		else mod(mid,r,cur*2+1,ind,val);
		a[cur]=max(a[cur*2],a[cur*2+1]);
	}
	int qry(int l,int r,int cur,int ql,int qr){
		if(ql>=r||qr<=l) return 0;
		if(ql<=l&&qr>=r) return a[cur];
		int mid=(l+r)/2;
		return max(qry(l,mid,cur*2,ql,qr),qry(mid,r,cur*2+1,ql,qr));
	}
}sgt;

signed main(){
  IO
	int n,m;cin >> n >> m;
	vector<int> a(n+1);
	for(int i=1;i<=n;i++){
		cin >> a[i];
	}
	vector<qr> Q(m);
	for(int i=0;i<m;i++){
		cin >> Q[i].l >> Q[i].r >> Q[i].k;
		Q[i].i=i;
	}
	sort(all(Q),[](qr aa,qr bb){
		return aa.r<bb.r;
	});
	int ind=0;
	stack<int> st;
	for(int i=0;i<m;i++){
		while(ind<=Q[i].r){
			while(!st.empty()&&a[ind]>=a[st.top()]) st.pop();
			if(!st.empty()){
				sgt.mod(1,n+1,1,st.top(),a[ind]+a[st.top()]);
			}
			st.push(ind);
			ind++;
		}
		int mx=sgt.qry(1,n+1,1,Q[i].l,Q[i].r+1);
		if(mx>Q[i].k) Q[i].ans=0;
		else Q[i].ans=1;
	}
	sort(all(Q),[](qr aa,qr bb){
		return aa.i<bb.i;
	});
	for(int i=0;i<m;i++){
		cout << Q[i].ans << '\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