Submission #163190

#	Time	Username	Problem	Language	Result	Execution time	Memory
163190		TadijaSebez	방벽 (JOI15_walls)	C++11	100 / 100	258 ms	17412 KiB

walls

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mt make_tuple
#define pb push_back
const int N=200050;
const int H=2*N;
int Us[N],usz,l[N],r[N],id[N];
int sgn(int x){ return x?x/abs(x):0;}
int nxt[N],pre[N],fir;
bool was[N];
ll sol[N];
int main()
{
	int n,m;
	scanf("%i %i",&n,&m);
	for(int i=1;i<=n;i++) scanf("%i %i",&l[i],&r[i]),id[i]=i;
	sort(id+1,id+1+n,[&](int i, int j){ return r[i]-l[i]<r[j]-l[j];});
	while(m--)
	{
		int x;scanf("%i",&x);
		if(!usz) Us[++usz]=x;
		else
		{
			if(Us[usz]==x) continue;
			if(usz==1 || sgn(Us[usz]-Us[usz-1])*sgn(x-Us[usz])==-1) Us[++usz]=x;
			else Us[usz]=x;
		}
	}
	fir=1;
	priority_queue<pair<int,int>> pq;
	int cnt=usz;
	ll sum=0;
	for(int i=2;i<=usz;i++)
	{
		nxt[i-1]=i;
		pre[i]=i-1;
		pq.push({-abs(Us[i]-Us[i-1]),i});
		sum+=abs(Us[i]-Us[i-1]);
	}
	for(int j=1,i;i=id[j],j<=n;j++)
	{
		while(cnt>2 && pq.size())
		{
			int d=-pq.top().first;
			int u=pq.top().second;
			if(d>r[i]-l[i]) break;
			pq.pop();
			if(u==fir || was[u] || abs(Us[u]-Us[pre[u]])!=d) continue;
			int v=pre[u];
			if(!pre[v])
			{
				fir=u;
				pre[u]=0;
				cnt--;
				sum-=d;
				was[v]=1;
			}
			else if(!nxt[u])
			{
				nxt[v]=0;
				cnt--;
				sum-=d;
				was[u]=1;
			}
			else
			{
				int x=pre[v],y=nxt[u];
				nxt[x]=y;
				pre[y]=x;
				was[u]=was[v]=1;
				sum-=abs(Us[u]-Us[v]);
				sum-=abs(Us[u]-Us[y]);
				sum-=abs(Us[v]-Us[x]);
				sum+=abs(Us[x]-Us[y]);
				cnt-=2;
				pq.push({-abs(Us[x]-Us[y]),y});
			}
		}
		int L=l[i],R=r[i];
		ll ans=sum;
		int sub=cnt-1;
		int u=fir;
		if(R<Us[u])
		{
			int dif=Us[u]-R;
			ans+=dif;
			L+=dif;R+=dif;
		}
		else if(L>Us[u])
		{
			int dif=L-Us[u];
			ans+=dif;
			L-=dif;R-=dif;
		}
		u=nxt[u];
		if(u)
		{
			ans-=abs(Us[u]-Us[pre[u]]);
			sub--;
			if(R<Us[u])
			{
				int dif=Us[u]-R;
				ans+=dif;
				L+=dif;R+=dif;
			}
			else if(L>Us[u])
			{
				int dif=L-Us[u];
				ans+=dif;
				L-=dif;R-=dif;
			}
		}
		ans-=(ll)sub*(R-L);
		sol[i]=ans;
	}
	for(int i=1;i<=n;i++) printf("%lld\n",sol[i]);
	return 0;
}

Compilation message (stderr)

walls.cpp: In function 'int main()':
walls.cpp:16:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
walls.cpp:17:50: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf("%i %i",&l[i],&r[i]),id[i]=i;
                        ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~
walls.cpp:21:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x;scanf("%i",&x);
         ~~~~~^~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 45 / 45
• Subtask 3: 45 / 45