Submission #467988

#	Time	Username	Problem	Language	Result	Execution time	Memory
467988		starplat	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	64 / 100	317 ms	24056 KiB

sortbooks

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define f first
#define s second
#define pll pair<ll,ll>
using namespace std;
ll n,m,w[(int)2e5+5],pos,val;
ll t[(int)(2e5+5)<<2],ans[(int)2e5+5];
vector<pll> v;
deque<int> q;
struct query{
	ll l,r,k,pos;
}e[(int)2e5+5];
bool s3(query a,query b)
{
	return a.l>b.l;
}
bool s1(pll a,pll b)
{
	return a.s>b.s;
}
bool s2(query a,query b)
{
	return a.pos<b.pos;
}
void update(int id,int x,int y,int tar,ll v)
{
	if (x==y){
		t[id]=max(t[id],v);
	}
	else {
		int mid=(x+y)/2;
		if (tar<=mid) update(id*2,x,mid,tar,v);
		else update(id*2+1,mid+1,y,tar,v);
		t[id]=max(t[id*2],t[id*2+1]);
	}
}
ll answer(int id,int x,int y,int lo,int hi)
{
	if (x>y||x>hi||y<lo) return 0;
	if (lo<=x&&y<=hi) return t[id];
	else {
		int mid=(x+y)/2;
		return max(answer(id*2,x,mid,lo,hi),answer(id*2+1,mid+1,y,lo,hi));
	}
}
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for (int i=1;i<=n;i++) cin>>w[i];
	q.pb(1);
	for (int i=2;i<=n;i++){
		while (!q.empty()){
			if (w[q.back()]<=w[i]) q.pop_back();
			else break;
		}
		if (!q.empty()) v.pb({i,q.back()});
		q.pb(i);
	}
	sort(v.begin(),v.end(),s1);
//	for (pll i:v) cout<<i.f<<" "<<i.s<<"\n";
	for (int i=0;i<m;i++) cin>>e[i].l>>e[i].r>>e[i].k,e[i].pos=i;
	sort(e,e+m,s3);
	int ptr=0,mx=v.size();
	for (int i=0;i<m;i++){
		while(ptr<mx && e[i].l<=v[ptr].s){
			//cout<<e[i].l<<" "<<v[ptr].f<<" "<<v[ptr].s<<"\n";
			update(1,1,n,v[ptr].f,w[v[ptr].f]+w[v[ptr].s]);
			++ptr;
		}
		//cout<<e[i].l<<" ";
		//cout<<answer(1,1,n,e[i].l,e[i].r)<<"\n";
		if (answer(1,1,n,e[i].l,e[i].r)<=e[i].k) ans[e[i].pos]=1;
		else ans[e[i].pos]=0;
	}
	for (int i=0;i<m;i++) cout<<ans[i]<<"\n";
	return 0;
}

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