Submission #549941

#	Time	Username	Problem	Language	Result	Execution time	Memory
549941		MilosMilutinovic	Food Court (JOI21_foodcourt)	C++14	0 / 100	1091 ms	39744 KiB

foodcourt

#include <bits/stdc++.h>
#define SIZE 250005
#define BT 256*1024*2

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

struct segtree
{
	ll mx[BT],mn[BT],lzy[BT],act[BT];
	segtree()
	{
		for(int i=0;i<BT;i++)
		{
			mx[i]=0;
			mn[i]=0;
			lzy[i]=0;
			act[i]=0;
		}
	}
	void push(int k,int l,int r)
	{
		if(l!=r)
		{
			mx[k*2+1]+=lzy[k];
			mn[k*2+1]+=lzy[k];
			mx[k*2+2]+=lzy[k];
			mn[k*2+2]+=lzy[k];
			lzy[k*2+1]+=lzy[k];
			lzy[k*2+2]+=lzy[k];
		}
		lzy[k]=0;
		if(act[k]==1)
		{
			if(l!=r)
			{
				mx[k*2+1]=0;
				mn[k*2+1]=0;
				mx[k*2+2]=0;
				mn[k*2+2]=0;
				act[k*2+1]=1;
				act[k*2+2]=1;
			}
			act[k]=0;
		}
	}
	void inc(int k,int l,int r,int a,int b,int v)
	{
		if(l>r||l>b||r<a) return;
		if(a<=l&&r<=b)
		{
			mn[k]+=v,mx[k]+=v,lzy[k]+=v;
			push(k,l,r);
			return;
		}
		push(k,l,r);
		int m=(l+r)/2;
		inc(k*2+1,l,m,a,b,v);
		inc(k*2+2,m+1,r,a,b,v);
		mx[k]=max(mx[k*2+1],mx[k*2+2]);
		mn[k]=min(mn[k*2+1],mn[k*2+2]);
	}
	void dec(int k,int l,int r,int a,int b,int v)
	{
		if(l>r||l>b||r<a) return;
		if(a<=l&&r<=b&&((mn[k]<=v?1:0)==(mx[k]<=v?1:0)))
		{
			if(mx[k]<=v)
			{
				mx[k]=0,mn[k]=0,act[k]=1;
			}
			else
			{
				mx[k]-=v,mn[k]-=v,lzy[k]-=v;
			}
			push(k,l,r);
			return;
		}
		push(k,l,r);
		int m=(l+r)/2;
		dec(k*2+1,l,m,a,b,v);
		dec(k*2+2,m+1,r,a,b,v);
		mx[k]=max(mx[k*2+1],mx[k*2+2]);
		mn[k]=min(mn[k*2+1],mn[k*2+2]);
	}
	ll query(int k,int l,int r,int i)
	{
		if(l==r) return mx[k];
		push(k,l,r);
		int m=(l+r)/2;
		if(i<=m) return query(k*2+1,l,m,i);
		else return query(k*2+2,m+1,r,i);
	}
}seg;
struct segg
{
	pair<ll,int> mn[BT];
	ll lzy[BT];
	segg()
	{
		for(int i=0;i<BT;i++) mn[i]={1e18,i};
	}
	void push(int k,int l,int r)
	{
		if(l!=r)
		{
			mn[k*2+1].first+=lzy[k];
			mn[k*2+2].first+=lzy[k];
			lzy[k*2+1]+=lzy[k];
			lzy[k*2+2]+=lzy[k];
		}
		lzy[k]=0;
	}
	void modify(int k,int l,int r,int i,ll v)
	{
		if(l==r)
		{
			mn[k]={v,i};
			return;
		}
		push(k,l,r);
		int m=(l+r)/2;
		if(i<=m) modify(k*2+1,l,m,i,v);
		else modify(k*2+2,m+1,r,i,v);
		mn[k]=min(mn[k*2+1],mn[k*2+2]);
	}
	void update(int k,int l,int r,int a,int b,int v)
	{
		if(l>r||l>b||r<a) return;
		if(a<=l&&r<=b)
		{
			mn[k].first+=v;
			lzy[k]+=v;
			push(k,l,r);
			return;
		}
		push(k,l,r);
		int m=(l+r)/2;
		update(k*2+1,l,m,a,b,v);
		update(k*2+2,m+1,r,a,b,v);
		mn[k]=min(mn[k*2+1],mn[k*2+2]);
	}
}seg1;

int n,m,q,t[SIZE],L[SIZE],k[SIZE],c[SIZE],ans[SIZE],ptr[SIZE];
ll R[SIZE],dat[SIZE],Q[SIZE];
vector<pair<ll,int>> Qs[SIZE];
void updf(int x,int v)
{
	for(x++;x<SIZE;x+=x&-x)dat[x]+=v;
}
ll getf(int x)
{
	ll r=0;
	for(x++;x>0;x-=x&-x)r+=dat[x];
	return r;
}
int main()
{
	scanf("%d%d%d",&n,&m,&q);
	for(int i=0;i<q;i++)
	{
		scanf("%d",&t[i]);
		if(t[i]==1)scanf("%d%d%d%d",&L[i],&R[i],&c[i],&k[i]),--L[i],--R[i];
		else if(t[i]==2)scanf("%d%d%d",&L[i],&R[i],&k[i]),--L[i],--R[i];
		else scanf("%d%lld",&L[i],&R[i]),--L[i];
	}
	for(int i=0;i<q;i++)
	{
		if(t[i]==1)
		{
			updf(L[i],k[i]);
			updf(R[i]+1,-k[i]);
			seg.inc(0,0,n-1,L[i],R[i],k[i]);
		}
		else if(t[i]==2)
		{
			seg.dec(0,0,n-1,L[i],R[i],k[i]);
		}
		else
		{
			ll tot=getf(L[i]),cur=seg.query(0,0,n-1,L[i]);
			Q[i]=(cur>=R[i]?tot-cur+R[i]:-1);
		}
	}
	for(int i=0;i<q;i++) if(t[i]==3&&Q[i]!=-1) Qs[L[i]].push_back({Q[i],i});
	for(int i=0;i<n;i++) sort(Qs[i].begin(),Qs[i].end());
	for(int i=0;i<n;i++)
	{
		if(!Qs[i].empty()) seg1.modify(0,0,n-1,i,Qs[i][0].first);
	}
	for(int i=0;i<q;i++)
	{
		if(t[i]==1)
		{
			seg1.update(0,0,n-1,L[i],R[i],-k[i]);
			while(seg1.mn[0].first<=0)
			{
				int id=seg1.mn[0].second;
				ans[Qs[id][ptr[id]].second]=c[i];
				ptr[id]++;
				if(ptr[id]==Qs[id].size()) seg1.modify(0,0,n-1,id,1e18);
				else seg1.modify(0,0,n-1,id,Qs[id][ptr[id]].first-Qs[id][ptr[id]-1].first);
			}
		}
	}
	for(int i=0;i<q;i++)
	{
		if(t[i]!=3) continue;
		if(Q[i]==-1) printf("0\n");
		else printf("%d\n",ans[i]);
	}
	return 0;
}

Compilation message (stderr)

foodcourt.cpp: In function 'int main()':
foodcourt.cpp:165:24: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'll*' {aka 'long long int*'} [-Wformat=]
  165 |   if(t[i]==1)scanf("%d%d%d%d",&L[i],&R[i],&c[i],&k[i]),--L[i],--R[i];
      |                       ~^            ~~~~~
      |                        |            |
      |                        int*         ll* {aka long long int*}
      |                       %lld
foodcourt.cpp:166:29: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'll*' {aka 'long long int*'} [-Wformat=]
  166 |   else if(t[i]==2)scanf("%d%d%d",&L[i],&R[i],&k[i]),--L[i],--R[i];
      |                            ~^          ~~~~~
      |                             |          |
      |                             int*       ll* {aka long long int*}
      |                            %lld
foodcourt.cpp:203:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  203 |     if(ptr[id]==Qs[id].size()) seg1.modify(0,0,n-1,id,1e18);
      |        ~~~~~~~^~~~~~~~~~~~~~~
foodcourt.cpp:161:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  161 |  scanf("%d%d%d",&n,&m,&q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
foodcourt.cpp:164:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  164 |   scanf("%d",&t[i]);
      |   ~~~~~^~~~~~~~~~~~
foodcourt.cpp:165:19: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  165 |   if(t[i]==1)scanf("%d%d%d%d",&L[i],&R[i],&c[i],&k[i]),--L[i],--R[i];
      |              ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:166:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  166 |   else if(t[i]==2)scanf("%d%d%d",&L[i],&R[i],&k[i]),--L[i],--R[i];
      |                   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:167:13: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  167 |   else scanf("%d%lld",&L[i],&R[i]),--L[i];
      |        ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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