oj.uz

답안 #56918

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
56918 2018-07-13T07:23:37 Z 윤교준(#1636) 방벽 (JOI15_walls) C++11
0 / 100
 508 ms 16416 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 int MAXN = 200005;
const int MAXQ = 200005;

struct BIT {
	BIT() { init(); }
	int d[MAXQ];
	void init() { fill(d, d+MAXQ, -INF); }
	void upd(int x, int r) {
		for(x += 2; x < MAXQ; x += rb(x))
			upmax(d[x], r);
	}
	int get(int x) {
		int r = -INF; for(x += 2; x; x -= rb(x))
			upmax(r, d[x]);
		return r;
	}
} bit;

multiset<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;

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]);
	for(int i = 1; i <= Q; i++) bit.upd(i, C[i]);

	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];
		//printf("oi=%d, i=%d, L=%d : at %d\n", oi, i, L[i], A[i]);

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

			X = (idx & 1) ? C[idx] : (C[idx] - l);

			vector<int> V; V.eb(idx);
			for(auto it = CH.lower_bound(idx);;) {
				it++; if(CH.end() == it) break;

				int uidx = *it, s, e;
				e = C[uidx]; s = e-l;

				V.eb(uidx);
				if(X < s || e < X) break;
			}

/*
			printf("idx=%d, l=%d, X=%d\n", idx, l, X);
			for(int v : V) printf("%d ", v);
			puts("");
*/

			for(int i = 1, n = sz(V), a, b; i < n; i++) {
				a = V[i-1]; b = V[i];
				EV.erase(pii(abs(C[a] - C[b]), a));
				if(i+1 < n) CH.erase(b);
				CHL -= abs(C[a] - C[b]);
			}

			int didx = -1, uidx = -1;

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

			//printf("didx=%d, uidx=%d\n", didx, uidx);
			//printf("CHL = %lld\n", CHL);
			
			if(0 < didx) {
				CH.erase(idx);
				CHL -= abs(C[idx] - C[didx]);
				EV.erase(pii(abs(C[idx] - C[didx]), didx));

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

		int ridx = *CH.begin();
		int ms = bit.get(ridx) - L[i];

		ll &ret = Ans[i];
		ret = CHL - ll(sz(CH)-1) * L[i];
		
		if(C[ridx] < ms) ret += abs(A[i] - ms) + abs(ms - C[ridx]);
		else if(1 < sz(CH)) ret += abs(C[ridx] - A[i]);
		else {
			if(C[ridx] < A[i]) ret = A[i] - C[ridx];
			else if(ms <= A[i]) ret = 0;
			else ret = ms - A[i];
		}
	}
}

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];
	}

/*
	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 9 ms 1912 KB Output is correct
2 Incorrect 508 ms 16416 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

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

Subtask #3
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 1912 KB Output is correct
2 Incorrect 508 ms 16416 KB Output isn't correct
3 Halted 0 ms 0 KB -