oj.uz

Submission #282922

# Submission time Handle Problem Language Result Execution time Memory
282922 2020-08-25T07:22:03 Z arnold518 None (JOI15_walls) C++14
10 / 100
 3000 ms 28112 KB 
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int MAXN = 2e5;
 
struct Data
{
	int l, r, p;
};
 
int N, M;
Data A[MAXN+10];
int B[MAXN+10], col[MAXN+10];
ll ans[MAXN+10];
 
int main()
{
	scanf("%d%d", &N, &M);
	for(int i=1; i<=N; i++)
	{
		scanf("%d%d", &A[i].l, &A[i].r);
		A[i].p=i;
	}
	for(int i=1; i<=M; i++) scanf("%d", &B[i]);
 
	M=unique(B+1, B+M+1)-B-1;
	vector<int> V;
	V.push_back(B[1]);
	for(int i=2; i<M; i++)
	{
		if(B[i-1]<B[i] && B[i+1]<B[i]) V.push_back(B[i]);
		else if(B[i-1]>B[i] && B[i+1]>B[i]) V.push_back(B[i]);
	}
	V.push_back(B[M]);
 
	for(int i=0; i<V.size(); i++) B[i+1]=V[i];
	M=V.size();
 
	sort(A+1, A+N+1, [&](const Data &p, const Data &q) { return p.r-p.l<q.r-q.l; });
	
	multiset<pii> S;
	set<int> S2;
 
	ll sum=0;
	for(int i=1; i<M; i++) S.insert({abs(B[i+1]-B[i]), i+1}), sum+=abs(B[i+1]-B[i]);
	for(int i=1; i<=M; i++) S2.insert(i), col[i]=(i+1)%2;
	for(int i=1; i<=N; i++)
	{
		int len=A[i].r-A[i].l;
		set<int> S3;
		for(auto it : S)
		{
			if(it.first<=len) S3.insert(it.second);
			else break;
		}
 
		while(!S3.empty())
		{
			int now=*S3.begin(), l, r;
			auto it=S2.find(now);
			if(col[now]==1) l=B[*prev(it)], r=B[*prev(it)]+len;
			else r=B[*prev(it)], l=B[*prev(it)]-len;
 
			vector<pii> V;
			for(; it!=S2.end(); it++)
			{
				V.push_back({abs(B[*it]-B[*prev(it)]), *it});
				if(!(l<=B[*it] && B[*it]<=r)) break;
			}
			if(it==S2.end())
			{
				for(auto jt : V)
				{
					if(S2.find(jt.second)!=S2.end()) S2.erase(jt.second);
					if(S3.find(jt.second)!=S3.end()) S3.erase(jt.second);
					if(S.find(jt)!=S.end()) S.erase(jt), sum-=jt.first;
				}
			}
			else if(col[*it]==col[now])
			{
				for(auto jt : V)
				{
					if(S2.find(jt.second)!=S2.end()) S2.erase(jt.second);
					if(S3.find(jt.second)!=S3.end()) S3.erase(jt.second);
					if(S.find(jt)!=S.end()) S.erase(jt), sum-=jt.first;
				}
				S2.insert(*it);
				auto pt=S2.find(*it), qt=prev(pt);
				S.insert({abs(B[*pt]-B[*qt]), *pt}); sum+=abs(B[*pt]-B[*qt]);
			}
			else
			{
				auto kt=prev(S2.find(now));
				V.push_back({abs(B[*kt]-B[*prev(kt)]), *kt});
				for(auto jt : V)
				{
					//printf("V %d %d\n", jt.first, jt.second);
					if(S2.find(jt.second)!=S2.end()) S2.erase(jt.second);
					if(S3.find(jt.second)!=S3.end()) S3.erase(jt.second);
					if(S.find(jt)!=S.end()) S.erase(jt), sum-=jt.first;
				}
				S2.insert(*it);
				auto pt=S2.find(*it), qt=prev(pt);
				S.insert({abs(B[*pt]-B[*qt]), *pt}); sum+=abs(B[*pt]-B[*qt]);
			}
			S3.erase(now);
		}
 
		//for(auto it : S) printf("%d %d\n", it.first, it.second);
		//printf("=> %lld %d\n", sum, A[i].p);

		bool flag=false;
		int l=A[i].l, r=A[i].r;
		for(auto it=S2.begin(); it!=S2.end(); it++)
		{
			if(B[*it]<l)
			{
				ans[A[i].p]+=l-B[*it];
				r-=l-B[*it]; l-=l-B[*it];
			}
			else if(r<B[*it])
			{
				ans[A[i].p]+=B[*it]-r;
				l+=B[*it]-r; r+=B[*it]-r;
			}
			//printf("!%d %lld\n", B[*it], ans[A[i].p]);
		}
		//printf("\n");
		//ans[A[i].p]=sum-(ll)S.size()*len;
	}
	for(int i=1; i<=N; i++) printf("%lld\n", ans[i]);
}

Compilation message

walls.cpp: In function 'int main()':
walls.cpp:40:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |  for(int i=0; i<V.size(); i++) B[i+1]=V[i];
      |               ~^~~~~~~~~
walls.cpp:116:8: warning: unused variable 'flag' [-Wunused-variable]
  116 |   bool flag=false;
      |        ^~~~
walls.cpp:22:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   22 |  scanf("%d%d", &N, &M);
      |  ~~~~~^~~~~~~~~~~~~~~~
walls.cpp:25:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   25 |   scanf("%d%d", &A[i].l, &A[i].r);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
walls.cpp:28:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   28 |  for(int i=1; i<=M; i++) scanf("%d", &B[i]);
      |                          ~~~~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1152 KB Output is correct
2 Correct 329 ms 20204 KB Output is correct
3 Correct 553 ms 28112 KB Output is correct
4 Correct 467 ms 26220 KB Output is correct
5 Correct 414 ms 27496 KB Output is correct
6 Correct 315 ms 23948 KB Output is correct
7 Correct 33 ms 2424 KB Output is correct
8 Correct 38 ms 2680 KB Output is correct

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3093 ms 2808 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1152 KB Output is correct
2 Correct 329 ms 20204 KB Output is correct
3 Correct 553 ms 28112 KB Output is correct
4 Correct 467 ms 26220 KB Output is correct
5 Correct 414 ms 27496 KB Output is correct
6 Correct 315 ms 23948 KB Output is correct
7 Correct 33 ms 2424 KB Output is correct
8 Correct 38 ms 2680 KB Output is correct
9 Execution timed out 3093 ms 2808 KB Time limit exceeded
10 Halted 0 ms 0 KB -