oj.uz

Submission #282882

# Submission time Handle Problem Language Result Execution time Memory
282882 2020-08-25T06:21:38 Z arnold518 None (JOI15_walls) C++14
45 / 100
 997 ms 32748 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;
	}
	M++; B[1]=0;
	for(int i=2; 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\n", sum);
		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:41:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |  for(int i=0; i<V.size(); i++) B[i+1]=V[i];
      |               ~^~~~~~~~~
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:29:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   29 |  for(int i=2; i<=M; i++) scanf("%d", &B[i]);
      |                          ~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 1152 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 2556 KB Output is correct
2 Correct 500 ms 15592 KB Output is correct
3 Correct 153 ms 11000 KB Output is correct
4 Correct 997 ms 32492 KB Output is correct
5 Correct 614 ms 25740 KB Output is correct
6 Correct 905 ms 32748 KB Output is correct
7 Correct 614 ms 25708 KB Output is correct
8 Correct 908 ms 32492 KB Output is correct
9 Correct 124 ms 10184 KB Output is correct
10 Correct 401 ms 31716 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 1152 KB Output isn't correct
2 Halted 0 ms 0 KB -