oj.uz

답안 #56937

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
56937 2018-07-13T08:58:14 Z 윤교준(#1636) 방벽 (JOI15_walls) C++11
0 / 100
 536 ms 16096 KB 
#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 bool debug = 0;
const int MAXN = 200005;
const int MAXQ = 200005;

multiset<pii> EV;
set<int> CH;
ll CHL, CMX;

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() {
	for(int i = 1; i < Q; i++)
		EV.insert(pii(abs(C[i+1] - C[i]), i));
	for(int i = 1; i <= Q; i++) CH.insert(i);
	for(int i = 1; i < Q; i++) CHL += abs(C[i+1] - C[i]);
	CMX = *max_element(C+1, C+Q+1);

	iota(O, O+N+1, 0);
	sort(O+1, O+N+1, [&](int a, int b) {
		return L[a] < L[b];
	});

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

		for(int idx, l; !EV.empty();) {
			tie(l, idx) = *EV.begin();
			if(L[i] < l) break;

			int tidx = -1;
			{
				auto it = CH.lower_bound(idx);
				it++;
				tidx = *it;
			}

			int pidx = -1;
			{
				auto it = CH.lower_bound(tidx);
				it++;
				if(CH.end() != it)
					pidx = *it;
			}
			int didx = -1;
			{
				auto it = CH.lower_bound(idx);
				if(CH.begin() != it) {
					it--;
					didx = *it;
				}
			}

			if(C[idx] < C[tidx]) {
				if(0 < pidx) EV.erase(f(tidx, pidx));
				EV.erase(f(tidx, idx));
				CH.erase(tidx);
				if(0 < pidx) CHL -= abs(C[pidx] - C[tidx]);
				CHL -= abs(C[tidx] - C[idx]);

				if(0 < pidx && 0 < didx) {
					EV.erase(f(idx, didx));
					CH.erase(idx);
					CHL -= abs(C[idx] - C[didx]);

					EV.insert(f(pidx, didx));
					CHL += abs(C[pidx] - C[didx]);
				} else if(0 < pidx) {
					EV.insert(f(pidx, idx));
					CHL += abs(C[pidx] - C[idx]);
				}
			} else {
				EV.erase(f(tidx, idx));
				if(0 < didx) EV.erase(f(idx, didx));
				CH.erase(idx);
				CHL -= abs(C[tidx] - C[idx]);
				if(0 < didx) CHL -= abs(C[idx] - C[didx]);

				if(0 < pidx && 0 < didx) {
					EV.erase(f(pidx, tidx));
					CH.erase(tidx);
					CHL -= abs(C[pidx] - C[tidx]);

					EV.insert(f(pidx, didx));
					CHL += abs(C[pidx] - C[didx]);
				} else if(0 < didx) {
					EV.insert(f(tidx, didx));
					CHL += abs(C[tidx] - C[didx]);
				}
			}
		}

		if(debug) {
			printf("SZ %d :: ", sz(CH));
			for(int v : CH) printf("%d ", v);
			puts("");

			printf("CHL = %lld\n", CHL);

			ll sum = 0;
			vector<int> V;
			for(int v : CH) V.eb(v);
			for(int i = 1; i < sz(V); i++)
				sum += abs(C[V[i-1]] - C[V[i]]);
			printf("REAL CHL = %lld\n", sum);
		}

		ll &ret = Ans[i];
		int X = A[i];

		if(debug) {
			printf("i=%d, X=%d\n", i, X);
		}

		if(1 < sz(CH)) {
			int ridx = *CH.begin(), pidx = -1;
			{
				auto it = CH.begin();
				it++;
				pidx = *it;
			}

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

			if(debug) {
				printf("ridx=%d, pidx=%d, def ret=%lld\n", ridx, pidx, ret);
			}

			if(C[ridx] < C[pidx]) ret += abs(C[ridx] - X);
			else ret += abs(ll(C[ridx]) - L[i] - X);

			if(debug) printf("dist = %lld\n", abs(ll(C[ridx] - L[i] - X)));
		} else {
			ll ms = CMX - L[i];
			int ridx = *CH.begin(), rx = C[ridx];
			if(rx < ms) exit(-1);

			if(rx < X) ret = X - rx;
			else if(ms <= X) ret = 0;
			else ret = ms - X;
		}
	}
}

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];
	for(int i = 1; i <= N; i++) L[i] = B[i] - A[i];

	{
		vector<int> V;
		V.eb(C[1]);

		for(int i = 2; i <= Q; i++)
			if(V.back() != C[i]) V.eb(C[i]);

		Q = sz(V);
		for(int i = 0; i < Q; i++)
			C[i+1] = V[i];
	}

	if(1 < Q) {
		if(C[2] < C[1]) {
			for(int i = 1; i <= Q; i++) C[i] = -C[i];
			for(int i = 1; i <= N; i++) A[i] = -B[i];
		}

		vector<int> V;
		V.eb(C[1]); V.eb(C[2]);

		for(int i = 3; i <= Q; i++) {
			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 = 0; i < Q; i++)
			C[i+1] = V[i];
	}

	if(debug) {
		printf("Q=%d\n", Q);
		for(int i = 1; i <= Q; i++) printf("%d ", C[i]);
		puts("");
	}

	process();

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

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 1144 KB Output is correct
2 Incorrect 536 ms 16096 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 46 ms 16096 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 1144 KB Output is correct
2 Incorrect 536 ms 16096 KB Output isn't correct
3 Halted 0 ms 0 KB -