Submission #56976

#	Time	Username	Problem	Language	Result	Execution time	Memory
56976		sebinkim	방벽 (JOI15_walls)	C++14	100 / 100	774 ms	38268 KiB

walls

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

priority_queue <pll> Q;
set <pll> S;
ll A[202020], B[202020], K[202020], T[202020];
ll P[202020], N[202020];
ll n, m, k, s, cnt;

int main()
{
	ll i, t, a, f, p;
	pll q;
	
	scanf("%lld%lld", &n, &m);
	
	for(i=1;i<=n;i++){
		scanf("%lld%lld", A+i, B+i);
		K[i] = i;
	}
	
	for(i=1;i<=m;i++){
		scanf("%lld", &a);
		
		if(k == 0) P[++k] = a;
		else if(k == 1){
			if(P[k] != a) P[++k] = a;
		}
		else{
			if(P[k-1] < P[k] && P[k] <= a) P[k] = a;
			else if(P[k-1] > P[k] && P[k] >= a) P[k] = a;
			else P[++k] = a;
		}
	}
	
	if(k == 1){
		for(i=1;i<=n;i++){
			if(A[i] <= a && a <= B[i]) printf("0\n");
			else if(a < A[i]) printf("%lld\n", A[i] - a);
			else printf("%lld\n", a - B[i]);
		}
		return 0;
	}
	
	for(i=1;i<k;i++){
		S.insert(pll(i, i+1));
		N[i] = i+1;
		
		Q.push(pll(-abs(P[i] - P[i+1]), i));
		s += abs(P[i] - P[i+1]);
		cnt ++;
	}
	
	sort(K+1, K+n+1, [&](int ca, int cb){
		return B[ca] - A[ca] < B[cb] - A[cb];
	});
	
	for(i=1;i<=n;i++){
		t = K[i];
		
		for(;S.size() > 1 && Q.size();){
			if(-Q.top().first <= B[t] - A[t]){
				f = -Q.top().first;
				p = Q.top().second;
				
				Q.pop();
				
				if(N[p] == -1 || abs(P[p] - P[N[p]]) != f) continue;
				
				auto it1 = S.lower_bound(pll(p, N[p]));
				auto it2 = it1; it2 ++;
				
				if(it2 == S.end()){
					s -= f; cnt --;
					N[p] = -1;
					S.erase(it1);
				}
				else if(it1 == S.begin()){
					s -= f; cnt --;
					N[p] = -1;
					S.erase(it1);
				}
				else{
					s -= f*2; cnt -= 2;
					
					auto it3 = it1; it3 --;
					ll x1 = it3->first, x2 = it1->first, x3 = it2->first, x4 = it2->second;
					
					N[x1] = x4;
					N[x2] = -1;
					N[x3] = -1;
					
					Q.push(pll(-abs(P[x1] - P[x4]), x1));
					
					it1 = S.lower_bound(pll(x1, x2)); S.erase(it1);
					it1 = S.lower_bound(pll(x2, x3)); S.erase(it1);
					it1 = S.lower_bound(pll(x3, x4)); S.erase(it1);
					
					S.insert(pll(x1, x4));
				}
			}
			else break;
		}
		
		q = *S.begin();
		
		if(S.size() == 1){
			ll a = P[q.first], b = P[q.second];
			if(abs(a - b) <= B[t] - A[t]){
				if(a > b) swap(a, b);
				if(A[t] <= a && b <= B[t]) T[t] = 0;
				else if(a <= A[t]) T[t] = A[t] - a;
				else T[t] = b - B[t];
				continue;
			}
		}
		
		if(P[q.first] < P[q.second]) T[t] = abs(A[t] - P[q.first]);
		else T[t] = abs(B[t] - P[q.first]);
		
		T[t] += s - cnt * (B[t] - A[t]);
	}
	
	for(i=1;i<=n;i++){
		printf("%lld\n", T[i]);
	}
	
	return 0;
}

Compilation message (stderr)

walls.cpp: In function 'int main()':
walls.cpp:19:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~~~~
walls.cpp:22:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld", A+i, B+i);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
walls.cpp:27:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &a);
   ~~~~~^~~~~~~~~~~~

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