Submission #253196

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

bulves

#include <bits/stdc++.h>

using namespace std;

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

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

struct segtree
{
	int l,r;
	pair<long long,int> mn;
	long long lz;
	segtree *p[2];
	
	void bd(int lh,int rh)
	{
		l=lh;
		r=rh;
		lz=0;
		if(l==r)
		{
			mn={wg[l],l};
		}
		else
		{
			int md=(l+r)/2;
			
			p[0]=new segtree;
			p[0]->bd(l,md);
			p[1]=new segtree;
			p[1]->bd(md+1,r);
			mn=min(p[0]->mn,p[1]->mn);
		}
	}
	inline void blc()
	{
		if(lz)
		{
			p[0]->mn.fr+=lz;
			p[0]->lz+=lz;
			p[1]->mn.fr+=lz;
			p[1]->lz+=lz;
			lz=0;
		}
	}
	void ud(int lh,int rh,long long w)
	{
		if(l>rh||r<lh);
		else if(l>=lh&&r<=rh)
		{
			mn.fr+=w;
			lz+=w;
		}
		else
		{
			blc();
			p[0]->ud(lh,rh,w);
			p[1]->ud(lh,rh,w);
			mn=min(p[0]->mn,p[1]->mn);
		}
	}
	pair<long long,int> qr(int lh,int 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()
{
	int i,ii,k,l,ww;
	long long w,z=0;
	pair<long long,int> tmp;
	
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		for(ii=0;ii<2;ii++)
		{
			scanf("%d",&a[ii][i]);
		}
		k=min(a[0][i],a[1][i]);
		for(ii=0;ii<2;ii++)
		{
			a[ii][i]-=k;
		}
	}
	w=0;
	for(i=n;i;i--)
	{
		w+=a[1][i];
		wg[i]=w+inf*!w;
		z+=w;
	}
	d=w;
	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;)
	{
		k=sg[1].mn.sc;
		w=sg[1].mn.fr;
		tmp=sg[0].qr(1,k);
		ww=min(min(tmp.fr,(long long)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:91:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
bulves.cpp:96:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&a[ii][i]);
    ~~~~~^~~~~~~~~~~~~~~~

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