제출 #1219232

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1219232		boclobanchat	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	0 / 100	3074 ms	121828 KiB

sortbooks

#include<bits/stdc++.h>
using namespace std;
struct query { int l,r,k,pos; };
const int MAXN=1e6+69;
const int INF=1e9;
int A[MAXN],pref[MAXN],fl[MAXN],fr[MAXN],fen[MAXN],val[MAXN],pos[MAXN];
bool ans[MAXN];
vector<query> vc[MAXN];
int getlog(long long n) { return 63-__builtin_clzll(n); }
void update(int i,int n,int val) { for(;i<=n;i+=i&-i) fen[i]+=val; }
int get(int i) { int ans=0;for(;i;i-=i&-i) ans+=fen[i];return ans; }
int walk(int n,int val) { if(!val) return 0;int ans=0;for(int i=getlog(n);i+1;i--) if(ans+(1<<i)<=n&&val>fen[ans+(1<<i)]) val-=fen[ans+=(1<<i)];return ans+1; }
void dnc(int l,int r,vector<query> vq)
{
	if(l==r)
	{
		for(auto v:vq) ans[v.pos]=true;
		return ;
	}
	int mid=(l+r)/2;
	vector<query> va,vb;
	for(auto v:vq) if(v.r<=mid) va.push_back(v);
	else if(mid<v.l) vb.push_back(v);
	else vc[v.r].push_back(v);
	int cnt=0,mx=0;
	val[0]=-INF;
	for(int i=l;i<=r;i++) val[++cnt]=A[i];
	sort(val+1,val+cnt+1);
	for(int i=l;i<=r;i++) pos[i]=lower_bound(val+1,val+cnt+1,A[i])-val;
	pref[mid+1]=fl[mid+1]=fr[mid]=0;
	for(int i=mid;i>=l;i--)
	{
		fl[i]=max(fl[i+1],val[walk(cnt,get(pos[i]-1))]+A[i]);
		pref[i]=max(pref[i+1],A[i]);
		update(pos[i],cnt,1);
	}
	for(int i=1;i<=cnt;i++) fen[i]=0;
	for(int i=mid+1;i<=r;i++)
	{
		fr[i]=fr[i-1];
		if(mx>A[i]) fr[i]=max(fr[i],mx+A[i]);
		mx=max(mx,A[i]);
		update(pos[i],cnt,1);
		for(auto v:vc[i])
		{
			bool ck=(fl[v.l]<=v.k&&fr[v.r]<=v.k);
			if(pref[v.l]+val[walk(cnt,get(lower_bound(val+1,val+cnt+1,v.k-pref[v.l])-val-1))]>v.k) ck=false;
			ans[v.pos]=ck;
		}
		vc[i].clear();
	}
	for(int i=1;i<=cnt;i++) fen[i]=0;
	dnc(l,mid,va);
	dnc(mid+1,r,vb);
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,q;
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>A[i];
    vector<query> vq;
    for(int i=1;i<=q;i++)
    {
		int l,r,k;
		cin>>l>>r>>k;
		vq.push_back({l,r,k,i});
	}
	dnc(1,n,vq);
	for(int i=1;i<=q;i++) cout<<ans[i]<<"\n";
}

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