제출 #453785

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
453785		CSQ31	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	1665 ms	119908 KiB

sortbooks

#pragma GCC optimize("Ofast") 
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define MOD (ll)(1e9+7)
#define INF (ll)(1e18)
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
ll gcd(ll a,ll b){if(!b)return a;else return gcd(b,a%b);}
struct node{
	ll mx = 0;
	node(ll a):mx(a){}
};
class pointseg{
	private:
	   int n;
	   vector<node>t;
	   vector<ll>a;
	   void upd(int v,int tl,int tr,int pos,node val){
		   if(tl == tr){
			   t[v] = val;
			   return;
		   }
		   int tm = (tl+tr)/2;
		   if(pos <= tm){
			   upd(2*v,tl,tm,pos,val);
		   }else{
			   upd(2*v+1,tm+1,tr,pos,val);
		   }
		   t[v] = merge(t[2*v],t[2*v+1]);
	   }
	   node query(int v,int l,int r,int tl,int tr){
		   if(l > r)return node(0);
		   if(l == tl && r == tr){
			   return t[v];
		   }
		   int tm = (tl+tr)/2;
		   return merge(query(2*v,l,min(r,tm),tl,tm),
		                query(2*v+1,max(l,tm+1),r,tm+1,tr));
	   }
	   void build(int v,int tl,int tr){
		   if(tl == tr){
			   t[v] = a[tl];
			   return;
		   }
		   int tm = (tl+tr)/2;
		   build(2*v,tl,tm);
		   build(2*v+1,tm+1,tr);
		   t[v] = merge(t[2*v],t[2*v+1]);
	   }
	public:
	   node merge(node a,node b){
		   return node(max(a.mx,b.mx));
	   }
	   void upd(int pos,node val){
		   upd(1,1,n,pos,val);
	   }
	   node query(int l,int r){
		   return query(1,l,r,1,n);
	   }
	   void build(){
		   build(1,1,n);
	   }
	   pointseg(int _n,vector<ll>_a ={}){
		   n = _n;
		   t.assign(4*n,node(0));
		   a = _a;
	   }
	   pointseg(){}
	   void reset(int _n,vector<ll>_a = {}){
		   n = _n;
		   t.clear();
		   t.assign(4*_n,node(0));
		   a = _a;
	   }
	
};
struct q{
	int l,idx,x;
	q(){}
	q(int a,int b,int c){l=a;idx=b;x=c;}
};
int main()
{
	owo
	int n,m;
	cin>>n>>m;
	vector<int>a(n+1),lf(n+1,0);
	for(int i=1;i<=n;i++)cin>>a[i];
	stack<int>stk;
	for(int i=1;i<=n;i++){
		while(!stk.empty() && a[i] >= a[stk.top()])stk.pop();
		if(!stk.empty())lf[i] = stk.top();
		stk.push(i);
	}
	vector<bool>ans(m);
	vector<vector<q>>qu(n+1);
	for(int i=0;i<m;i++){
		int l,r,x;
		cin>>l>>r>>x;
		qu[r].pb(q(l,i,x));
	}
	//for(int i=1;i<=n;i++)cout<<lf[i]<<" ";
	//cout<<'\n';
	pointseg s(n);
	for(int i=1;i<=n;i++){
		if(lf[i])s.upd(lf[i],a[i]+a[lf[i]]);
		for(auto y:qu[i]){
			ans[y.idx] = (s.query(y.l,i).mx <= y.x);
		}
	}
	for(int i=0;i<m;i++)cout<<ans[i]<<'\n';
	
}

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