Submission #253189

#	Time	Username	Problem	Language	Result	Execution time	Memory
253189		Pyqe	Potatoes and fertilizers (LMIO19_bulves)	C++14	30 / 100	1100 ms	144120 KiB

bulves

#include <bits/stdc++.h>

using namespace std;

#define mp make_pair
#define fr first
#define sc second

long long n,d=0,nn=0,a[2][500069],wg[500069],inf=1e18;

struct segtree
{
	long long l,r,lz;
	pair<long long,long long> mn;
	segtree *p[2];
	
	void bd(long long lh,long long rh)
	{
		l=lh;
		r=rh;
		lz=0;
		if(l==r)
		{
			mn={wg[l],l};
		}
		else
		{
			long long ii,md=(l+r)/2;
			
			for(ii=0;ii<2;ii++)
			{
				p[ii]=new segtree;
				p[ii]->bd(!ii?l:md+1,!ii?md:r);
			}
			mn=min(p[0]->mn,p[1]->mn);
		}
	}
	void blc()
	{
		long long ii;
		
		for(ii=0;ii<2;ii++)
		{
			p[ii]->mn.fr+=lz;
			p[ii]->lz+=lz;
		}
		lz=0;
	}
	void ud(long long lh,long long rh,long long w)
	{
		if(l>rh||r<lh);
		else if(l>=lh&&r<=rh)
		{
			mn.fr+=w;
			lz+=w;
		}
		else
		{
			long long ii;
			
			blc();
			for(ii=0;ii<2;ii++)
			{
				p[ii]->ud(lh,rh,w);
			}
			mn=min(p[0]->mn,p[1]->mn);
		}
	}
	pair<long long,long long> qr(long long lh,long long rh)
	{
		if(l>rh||r<lh)
		{
			return {inf,-1};
		}
		else if(l>=lh&&r<=rh)
		{
			return mn;
		}
		else
		{
			blc();
			return min(p[0]->qr(lh,rh),p[1]->qr(lh,rh));
		}
	}
}
sg[2];

int main()
{
	long long i,ii,j,k,l,w,ww,z=0;
	pair<long long,long long> tmp;
	
	scanf("%lld",&n);
	for(i=1;i<=n;i++)
	{
		for(ii=0;ii<2;ii++)
		{
			scanf("%lld",&a[ii][i]);
		}
	}
	k=0;
	for(i=n;i;i--)
	{
		k+=a[1][i];
		wg[i]=k+inf*!k;
		z+=k;
	}
	d=k;
	sg[0].bd(1,n);
	k=0;
	for(i=1;i<=n;i++)
	{
		k+=(wg[i]<=0||wg[i]==inf)*2-1;
		if(a[0][i])
		{
			wg[i]=k;
		}
		else
		{
			wg[i]=inf;
		}
	}
	sg[1].bd(1,n);
	for(;d;)
	{
		tmp=sg[1].qr(1,n);
		k=tmp.sc;
		w=tmp.fr;
		tmp=sg[0].qr(1,k);
		ww=min(min(tmp.fr,a[0][k]),d);
		z+=w*ww;
		d-=ww;
		a[0][k]-=ww;
		if(!a[0][k])
		{
			sg[1].ud(k,k,inf);
		}
		sg[0].ud(1,k,-ww);
		for(;1;)
		{
			tmp=sg[0].qr(1,k);
			l=tmp.sc;
			w=tmp.fr;
			if(w)
			{
				break;
			}
			sg[1].ud(l,n,2);
			sg[0].ud(l,l,inf);
		}
	}
	printf("%lld\n",z);
}

Compilation message (stderr)

bulves.cpp: In function 'int main()':
bulves.cpp:90:17: warning: unused variable 'j' [-Wunused-variable]
  long long i,ii,j,k,l,w,ww,z=0;
                 ^
bulves.cpp:93:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld",&n);
  ~~~~~^~~~~~~~~~~
bulves.cpp:98:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%lld",&a[ii][i]);
    ~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 24
• Subtask 2: 0 / 10
• Subtask 3: 20 / 20
• Subtask 4: 10 / 10
• Subtask 5: 0 / 36