Submission #389829

#	Time	Username	Problem	Language	Result	Execution time	Memory
389829		ogibogi2004	Food Court (JOI21_foodcourt)	C++14	100 / 100	959 ms	112452 KiB

foodcourt

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN=250060;
struct node
{
	ll lazymax;
	ll lazyadd;
	ll maxhere;
};
node tree[4*MAXN];
void build(ll l,ll r,ll idx)
{
	tree[idx].maxhere=0;
	tree[idx].lazymax=0;
	tree[idx].lazyadd=0;
	if(l==r)return;
	ll mid=(l+r)/2;
	build(l,mid,idx*2);
	build(mid+1,r,idx*2+1);
}
node merge(node n1,node n2)
{
	node ret;
	ret.maxhere=max(0ll,max(max(n1.maxhere,n1.lazymax)+n1.lazyadd,max(n2.lazymax,n2.maxhere)+n2.lazyadd));
	ret.lazyadd=0;
	ret.lazymax=0;
	return ret;
}
void push_lazy(ll l,ll r,ll idx)
{
	//cout<<"&& "<<l<<" "<<r<<" "<<tree[idx].maxhere<<" "<<tree[idx].lazymax<<" "<<tree[idx].lazyadd<<endl;
	
	tree[idx].maxhere=max(tree[idx].maxhere,tree[idx].lazymax);
	tree[idx].maxhere+=tree[idx].lazyadd;
	tree[idx].maxhere=max(tree[idx].maxhere,0ll);
	//cout<<"& "<<tree[idx].maxhere<<endl;
	if(l!=r)
	{
		ll b1=tree[idx*2].lazymax;
		ll c1=tree[idx*2].lazyadd;
		ll b2=tree[idx].lazymax;
		ll c2=tree[idx].lazyadd;
		//if(l==4&&r==6)cout<<b1<<" "<<c1<<" "<<b2<<" "<<c2<<endl;
		tree[idx*2].lazymax=max(b1,b2-c1);
		tree[idx*2].lazyadd=c1+c2;
	}
	if(l!=r)
	{
		ll b1=tree[idx*2+1].lazymax;
		ll c1=tree[idx*2+1].lazyadd;
		ll b2=tree[idx].lazymax;
		ll c2=tree[idx].lazyadd;
		tree[idx*2+1].lazymax=max(b1,b2-c1);
		tree[idx*2+1].lazyadd=c1+c2;
	}
	tree[idx].lazymax=0;
	tree[idx].lazyadd=0;
}
void update(ll l,ll r,ll idx,ll ql,ll qr,ll val)
{
	push_lazy(l,r,idx);
	if(l>qr)return;
	if(r<ql)return;
	if(l>=ql&&r<=qr)
	{
		
		tree[idx].lazyadd+=val;
		push_lazy(l,r,idx);
		return;
	}
	ll mid=(l+r)/2;
	update(l,mid,idx*2,ql,qr,val);
	update(mid+1,r,idx*2+1,ql,qr,val);
	tree[idx]=merge(tree[idx*2],tree[idx*2+1]);
}
ll ask(ll l,ll r,ll idx,ll qi)
{
	/*if(l==4&&r==6)
		{
			cout<<tree[idx].lazymax<<" "<<tree[idx].lazyadd<<endl;
		}*/
	push_lazy(l,r,idx);
	if(l>qi||r<qi)return 0;
	if(l==r)return tree[idx].maxhere;
	ll mid=(l+r)/2;
	return max(ask(l,mid,idx*2,qi),ask(mid+1,r,idx*2+1,qi));
}
ll n,m,q;
void prll(ll l,ll r,ll idx)
{
	cout<<l<<" "<<r<<" "<<tree[idx].maxhere<<" "<<tree[idx].lazymax<<" "<<tree[idx].lazyadd<<endl;
	if(l==r)return;
	ll mid=(l+r)/2;
	prll(l,mid,idx*2);
	prll(mid+1,r,idx*2+1);
}
void updateMax(ll l,ll r,ll idx,ll ql,ll qr)
{
	push_lazy(l,r,idx);
	if(l>qr||r<ql)return;
	if(l>=ql&&r<=qr)
	{
		push_lazy(l,r,idx);
		return;
	}
	ll mid=(l+r)/2;
	updateMax(l,mid,idx*2,ql,qr);
	updateMax(mid+1,r,idx*2+1,ql,qr);
	tree[idx]=merge(tree[idx*2],tree[idx*2+1]);
}
struct BIT
{
	ll fen[MAXN];
	void init()
	{
		memset(fen,0,sizeof(fen));
	}
	void update(ll idx,ll val)
	{
		idx++;
		for(;idx<MAXN;idx+=idx&(-idx))
		{
			fen[idx]+=val;
		}
	}
	ll ask(ll idx)
	{
		idx++;
		ll ret=0;
		for(;idx>0;idx-=idx&(-idx))
		{
			ret+=fen[idx];
		}
		return ret;
	}
}ogi;
ll ans[MAXN];
vector<pair<ll,ll> >bs[MAXN];
struct upd
{
	ll type,l,r,c,k;
};
vector<upd>v;
struct query
{
	ll ind,b,pos;
};
vector<query>z;
ll low[MAXN],high[MAXN],ans1[MAXN];
vector<pair<query,ll> >toCheck[MAXN];
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n>>m>>q;
	build(1,n,1);
	for(ll i=0;i<q;++i)
	{
		ll type;
		cin>>type;
		if(type==1)
		{
			ll l,r,c,k;
			cin>>l>>r>>c>>k;
			update(1,n,1,l,r,k);
			ogi.update(l,+k);
			ogi.update(r+1,-k);
			v.push_back({type,l,r,c,k});
		}
		else if(type==2)
		{
			ll l,r,k;
			cin>>l>>r>>k;
			update(1,n,1,l,r,-k);
			v.push_back({type,l,r,0,k});
			//updateMax(1,n,1,l,r);
		}
		else
		{
			ll a,b;
			cin>>a>>b;
			ll t=ask(1,n,1,a);
			if(t>=b)
			{
				bs[a].push_back({ogi.ask(a)-(t-b),i});
			}
			v.push_back({type,0,0,0,0});
			//cout<<t<<endl;
		}
		//cout<<"------\n";
		//prll(1,n,1);
		//cout<<"-----\n";
	}
	/*cin>>n>>q;
	build(1,n,1);
	for(ll i=0;i<q;i++)
	{
		ll l,r,val;
		cin>>l>>r>>val;
		update(1,n,1,l,r,val);
		ll j;
		cin>>j;
		cout<<ask(1,n,1,j)<<endl;
		for(j=1;j<=n;j++)
		{
			cout<<ask(1,n,1,j)<<" ";
		}
		cout<<endl;
		prll(1,n,1);
	}*/
	for(ll i=1;i<=n;i++)
	{
		for(ll j=0;j<bs[i].size();j++)
		{
			z.push_back({i,bs[i][j].first,bs[i][j].second});
		}
	}
	for(ll i=0;i<z.size();i++)
	{
		low[i]=0;
		high[i]=q-1;
		//cout<<z[i].ind<<" "<<z[i].b<<" "<<z[i].pos<<endl;
	}
	ogi.init();
	for(ll step=0;step<19;++step)
	{
		for(ll i=0;i<z.size();++i)
		{
			if(low[i]<=high[i])
			{
				ll mid=(low[i]+high[i])/2;
				toCheck[mid].push_back({z[i],i});
			}
		}
		for(ll j=0;j<v.size();++j)
		{
			if(v[j].type==1)
			{
				ogi.update(v[j].l,+v[j].k);
				ogi.update(v[j].r+1,-v[j].k);
			}
			for(auto xd:toCheck[j])
			{
				if(ogi.ask(xd.first.ind)>=xd.first.b)
				{
					ans1[xd.second]=j;
					high[xd.second]=j-1;
				}
				else low[xd.second]=j+1;
			}
			toCheck[j].clear();
		}
		ogi.init();
	}
	for(ll i=0;i<z.size();++i)
	{
		//cout<<ans1[i]<<" "<<z[i].pos<<endl;
		ans[z[i].pos+1]=v[ans1[i]].c;
	}
	for(ll i=1;i<=q;++i)
	{
		if(v[i-1].type==3)
		{
			cout<<ans[i]<<'\n';
		}
	}
return 0;
}
/*
3 5 7
1 2 3 5 2
1 1 2 2 4
3 2 3
2 1 3 3
3 1 2
1 2 3 4 2
3 3 2
*/

Compilation message (stderr)

foodcourt.cpp: In function 'int main()':
foodcourt.cpp:215:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  215 |   for(ll j=0;j<bs[i].size();j++)
      |              ~^~~~~~~~~~~~~
foodcourt.cpp:220:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  220 |  for(ll i=0;i<z.size();i++)
      |             ~^~~~~~~~~
foodcourt.cpp:229:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  229 |   for(ll i=0;i<z.size();++i)
      |              ~^~~~~~~~~
foodcourt.cpp:237:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<upd>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  237 |   for(ll j=0;j<v.size();++j)
      |              ~^~~~~~~~~
foodcourt.cpp:257:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  257 |  for(ll i=0;i<z.size();++i)
      |             ~^~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 5 / 5
• Subtask 3: 7 / 7
• Subtask 4: 21 / 21
• Subtask 5: 15 / 15
• Subtask 6: 13 / 13
• Subtask 7: 26 / 26
• Subtask 8: 11 / 11