oj.uz

Submission #163190

# Submission time Handle Problem Language Result Execution time Memory
163190 2019-11-11T17:57:25 Z TadijaSebez None (JOI15_walls) C++11
100 / 100
 258 ms 17412 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 632 KB Output is correct
2 Correct 67 ms 6100 KB Output is correct
3 Correct 75 ms 6500 KB Output is correct
4 Correct 66 ms 6448 KB Output is correct
5 Correct 74 ms 6500 KB Output is correct
6 Correct 56 ms 6500 KB Output is correct
7 Correct 27 ms 2168 KB Output is correct
8 Correct 36 ms 2296 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1792 KB Output is correct
2 Correct 98 ms 6508 KB Output is correct
3 Correct 119 ms 9848 KB Output is correct
4 Correct 236 ms 15636 KB Output is correct
5 Correct 206 ms 14264 KB Output is correct
6 Correct 240 ms 15700 KB Output is correct
7 Correct 203 ms 14256 KB Output is correct
8 Correct 231 ms 15760 KB Output is correct
9 Correct 115 ms 9488 KB Output is correct
10 Correct 193 ms 14820 KB Output is correct

Subtask #3
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 632 KB Output is correct
2 Correct 67 ms 6100 KB Output is correct
3 Correct 75 ms 6500 KB Output is correct
4 Correct 66 ms 6448 KB Output is correct
5 Correct 74 ms 6500 KB Output is correct
6 Correct 56 ms 6500 KB Output is correct
7 Correct 27 ms 2168 KB Output is correct
8 Correct 36 ms 2296 KB Output is correct
9 Correct 20 ms 1792 KB Output is correct
10 Correct 98 ms 6508 KB Output is correct
11 Correct 119 ms 9848 KB Output is correct
12 Correct 236 ms 15636 KB Output is correct
13 Correct 206 ms 14264 KB Output is correct
14 Correct 240 ms 15700 KB Output is correct
15 Correct 203 ms 14256 KB Output is correct
16 Correct 231 ms 15760 KB Output is correct
17 Correct 115 ms 9488 KB Output is correct
18 Correct 193 ms 14820 KB Output is correct
19 Correct 219 ms 15972 KB Output is correct
20 Correct 258 ms 17412 KB Output is correct
21 Correct 221 ms 15972 KB Output is correct
22 Correct 235 ms 16484 KB Output is correct
23 Correct 222 ms 15748 KB Output is correct
24 Correct 248 ms 17252 KB Output is correct
25 Correct 163 ms 11576 KB Output is correct
26 Correct 162 ms 12280 KB Output is correct
27 Correct 224 ms 16840 KB Output is correct