Submission #56963

#	Time	Username	Problem	Language	Result	Execution time	Memory
56963		youngyojun	방벽 (JOI15_walls)	C++11	100 / 100	1181 ms	47688 KiB

walls

#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define befv(V) ((V)[(sz(V)-2)])
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define clv(V) (V).clear()
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define rb(x) ((x)&(-(x)))
#define cb(x) (x)=(!(x))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int MAXN = 200005;
const int MAXQ = 200005;

set<pii> EV;
set<int> CH; ll CHL;

int A[MAXN], B[MAXN], L[MAXN], O[MAXN];
int C[MAXQ];

ll Ans[MAXN];
int N, Q;

pii f(int a, int b) { return pii(abs(C[a] - C[b]), min(a, b)); }

void process() {
	if(1 == Q) {
		for(int i = 1; i <= N; i++) {
			ll &ret = Ans[i];
			if(A[i] <= C[1] && C[1] <= B[i]) ret = 0;
			else if(B[i] < C[1]) ret = C[1] - B[i];
			else ret = A[i] - C[1];
		}
		return;
	}

	for(int i = 1; i <= Q; i++) CH.insert(i);
	for(int i = 1; i < Q; i++) EV.insert(f(i, i+1));
	for(int i = 1; i < Q; i++) CHL += abs(C[i+1] - C[i]);

	for(int oi = 1, i; oi <= N; oi++) {
		i = O[oi];

		for(int a, b, l; 2 < sz(CH) && !EV.empty();) {
			tie(l, a) = *EV.begin();
			if(L[i] < l) break;

			b = *next(CH.lower_bound(a));
			EV.erase(f(a, b));
			CHL -= abs(C[a] - C[b]);

			if(*CH.begin() == a) {
				CH.erase(a);
				continue;
			} else if(*prev(CH.end()) == b) {
				CH.erase(b);
				continue;
			}

			int u = *next(CH.lower_bound(b));
			int d = *prev(CH.lower_bound(a));

			EV.erase(f(u, b));
			EV.erase(f(a, d));
			EV.insert(f(u, d));
			CH.erase(a); CH.erase(b);

			CHL -= abs(C[u] - C[b]);
			CHL -= abs(C[a] - C[d]);
			CHL += abs(C[u] - C[d]);
		}

		ll &ret = Ans[i];
		int X = A[i];
		int a = *CH.begin(), b = *next(CH.begin());

		if(2 < sz(CH)) {
			ret = CHL - ll(sz(CH) - 1) * L[i];

			if(C[a] < C[b]) ret += abs(C[a] - X);
			else ret += abs(C[a] - B[i]);
		} else {
			if(C[a] < C[b]) {
				ret = abs(C[a] - X);
				int Y = C[a] + L[i];
				if(Y < C[b]) ret += abs(C[b] - Y);

				if(C[b]-C[a] <= L[i]) upmin(ret, (ll)min(abs(B[i] - C[b]), abs(A[i] - C[a])));
				if(A[i] <= C[a] && C[b] <= B[i]) ret = 0;
			} else {
				ret = abs(C[a] - B[i]);
				int Y = C[a] - L[i];
				if(C[b] < Y) ret += abs(C[b] - Y);

				if(C[a]-C[b] <= L[i]) upmin(ret, (ll)min(abs(B[i] - C[a]), abs(A[i] - C[b])));
				if(A[i] <= C[b] && C[a] <= B[i]) ret = 0;
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);

	cin >> N >> Q;
	for(int i = 1; i <= N; i++) cin >> A[i] >> B[i];
	for(int i = 1; i <= Q; i++) cin >> C[i];

	{
		vector<int> V; V.eb(C[1]);
		for(int i = 2; i <= Q; i++) {
			if(V.back() == C[i]) continue;
			for(; 1 < sz(V) && (befv(V) < V.back()) == (V.back() < C[i]); V.pop_back());
			V.eb(C[i]);
		}
		Q = sz(V);
		for(int i = 1; i <= Q; i++) C[i] = V[i-1];
	}

	for(int i = 1; i <= N; i++) L[i] = B[i] - A[i];
	iota(O, O+N+1, 0); sort(O+1, O+N+1, [&](int a, int b) { return L[a] < L[b]; });

	process();

	for(int i = 1; i <= N; i++) printf("%lld\n", Ans[i]);
	return 0;
}

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