Submission #430196

#	Time	Username	Problem	Language	Result	Execution time	Memory
430196		Pyqe	Treatment Project (JOI20_treatment)	C++14	100 / 100	879 ms	80664 KiB

treatment

#include <bits/stdc++.h>

using namespace std;

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

const long long inf=1e18;
long long ln,n,wg[100069],com[100069],nr[100069];
pair<long long,pair<long long,long long>> a[100069];
pair<long long,long long> xy[100069],as[100069];
priority_queue<pair<long long,long long>> pq;

struct segtree
{
	long long l,r,nn;
	vector<long long> vl,dsu;
	segtree *p[2];
	
	long long fd(long long x)
	{
		if(dsu[x]!=x)
		{
			dsu[x]=fd(dsu[x]);
		}
		return dsu[x];
	}
	void bd(long long lh,long long rh)
	{
		l=lh;
		r=rh;
		nn=0;
		vl.push_back(0);
		dsu.push_back(0);
		if(l<r)
		{
			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);
			}
		}
	}
	void ins(long long x,long long w)
	{
		if(l>x||r<x);
		else
		{
			nn++;
			vl.push_back(w);
			dsu.push_back(nn);
			if(!(l>=x&&r<=x))
			{
				long long ii;
				
				for(ii=0;ii<2;ii++)
				{
					p[ii]->ins(x,w);
				}
			}
		}
	}
	void qr(long long lh,long long rh,long long ub,long long w)
	{
		if(l>rh||r<lh);
		else if(l>=lh&&r<=rh)
		{
			long long p;
			
			for(;nn&&xy[vl[fd(1)]].sc<=ub;dsu[fd(1)]=fd((fd(1)+1)%(nn+1)))
			{
				p=vl[fd(1)];
				if(w+wg[p]<nr[p])
				{
					pq.push({-w-wg[p],p});
					nr[p]=w+wg[p];
				}
			}
		}
		else
		{
			long long ii;
			
			for(ii=0;ii<2;ii++)
			{
				p[ii]->qr(lh,rh,ub,w);
			}
		}
	}
}
sg;

int main()
{
	long long i,k,l,w,ti,p,x,z=inf;
	
	scanf("%lld%lld",&ln,&n);
	xy[0]={inf,inf};
	for(i=1;i<=n;i++)
	{
		scanf("%lld%lld%lld%lld",&ti,&k,&l,wg+i);
		a[i]={ti,{k,l}};
		xy[i]={k+ti,k-ti};
		com[i]=k+ti;
		as[i]={k-ti,i};
		nr[i]=inf;
	}
	sort(com+1,com+n+1);
	sort(as+1,as+n+1);
	sg.bd(1,n);
	for(i=1;i<=n;i++)
	{
		p=as[i].sc;
		x=xy[p].fr;
		sg.ins(lower_bound(com+1,com+n+1,x)-com,p);
	}
	for(i=1;i<=n;i++)
	{
		k=a[i].sc.fr;
		if(k==1)
		{
			pq.push({-wg[i],i});
			nr[i]=wg[i];
		}
	}
	for(;!pq.empty();)
	{
		w=-pq.top().fr;
		p=pq.top().sc;
		pq.pop();
		ti=a[p].fr;
		l=a[p].sc.sc;
		sg.qr(1,upper_bound(com+1,com+n+1,l+1+ti)-com-1,l+1-ti,w);
	}
	for(i=1;i<=n;i++)
	{
		l=a[i].sc.sc;
		if(l==ln)
		{
			z=min(z,nr[i]);
		}
	}
	if(z==inf)
	{
		z=-1;
	}
	printf("%lld\n",z);
}

Compilation message (stderr)

treatment.cpp: In function 'int main()':
treatment.cpp:100:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |  scanf("%lld%lld",&ln,&n);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
treatment.cpp:104:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |   scanf("%lld%lld%lld%lld",&ti,&k,&l,wg+i);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 30 / 30
• Subtask 4: 61 / 61