Submission #677537

#	Time	Username	Problem	Language	Result	Execution time	Memory
677537		onjo0127	방벽 (JOI15_walls)	C++17	0 / 100	3076 ms	18524 KiB

walls

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using tiii = tuple<int, int, int>;
using ll = long long;

ll ans[200009];
int N, M, A[200009], B[200009], L[200009], R[200009], V[200009];
bool C[200009];

struct fenwick {
	ll F[200009];
	ll get(int x) {
		++x;
		ll s = 0;
		for(int i=x; i>=1; i-=(i&-i)) s += F[i];
		return s;
	}
	void upd(int x, int y) {
		++x;
		for(int i=x; i<=M; i+=(i&-i)) F[i] += y;
	}
} F1, F2;

int dst(int l, int r, int x) {
	if(x < l) return l-x;
	if(l <= x && x <= r) return 0;
	if(r < x) return x-r;
}

int main() {
	vector<int> W;
	scanf("%d%d", &N, &M);
	for(int i=1; i<=N; i++) {
		scanf("%d%d", &A[i], &B[i]);
		W.push_back(i);
	}
	sort(W.begin(), W.end(), [&](int p, int q) { return B[p] - A[p] < B[q] - A[q]; });
	vector<int> P;
	while(M--) {
		int x; scanf("%d", &x);
		int K = P.size();
		if(K <= 1) P.push_back(x);
		else {
			if(P[K-2] < P[K-1] && P[K-1] <= x) P.pop_back();
			else if(P[K-2] > P[K-1] && P[K-1] >= x) P.pop_back();
			P.push_back(x);
		}
	}
	M = P.size();
	set<int> S;
	priority_queue<tiii> pq;
	L[0] = R[0] = P[0];
	vector<int> E = {0};
	for(int i=0; i<M; i++) {
		S.insert(i);
		if(i) {
			V[i] = max(P[i] - P[i-1], P[i-1] - P[i]);
			F1.upd(i, V[i]);
			F2.upd(i, +1);
			L[i] = min(L[i-1], P[i]);
			R[i] = max(R[i-1], P[i]);
			if(L[i-1] != L[i] || R[i-1] != R[i]) {
				int K = E.size();
				if(K <= 1) E.push_back(i);
				else {
					if(P[E[K-2]] < P[E[K-1]] && P[E[K-1]] <= P[i]) E.pop_back();
					else if(P[E[K-2]] > P[E[K-1]] && P[E[K-1]] >= P[i]) E.pop_back();
					E.push_back(i);
				}
			}
			pq.push({-V[i], i-1, i});
		}
	}
	for(auto& it: E) C[it] = 1;

	int k = 0;
	for(auto& it: W) {
		while(pq.size()) {
			int g, a, b; tie(g, a, b) = pq.top(); g = -g;
			if(g > B[it] - A[it]) break;
			pq.pop();
			if(*S.rbegin() == b && !C[b]) {
				C[b] = 1; F1.upd(b, -V[b]); F2.upd(b, -1); S.erase(b);
				continue;
			}
			if(C[a] || C[b]) continue;

			C[a] = 1; F1.upd(a, -V[a]); F2.upd(a, -1); S.erase(a);
			C[b] = 1; F1.upd(b, -V[b]); F2.upd(b, -1); S.erase(b);
			auto nt = S.upper_bound(b), pt = prev(nt);
			F1.upd(*nt, V[a] - V[b]); V[*nt] += V[a] - V[b];
			pq.push({-V[*nt], *pt, *nt});
		}
		while(k+1 < E.size() && max(P[E[k+1]] - P[E[k]], P[E[k]] - P[E[k+1]]) <= B[it] - A[it]) ++k;
		k = max(0, k-1);
		int x = E[k];
		while(1) {
			ans[it] += dst(A[it], B[it], P[x]);
			int d = 0;
			if(P[x] < A[it]) d = P[x] - A[it];
			if(B[it] < P[x]) d = P[x] - B[it];
			A[it] += d; B[it] += d;
			auto nt = S.upper_bound(x);
			if(nt == S.end()) break;
			x = *nt;
		}
		/*
		ans[it] = dst(A[it], B[it], P[E[k]]);
		auto nt = S.upper_bound(E[k]);
		if(nt != S.end()) {
			int d = 0;
			if(P[E[k]] < A[it]) d = P[E[k]] - A[it];
			if(B[it] < P[E[k]]) d = P[E[k]] - B[it];
			ans[it] += dst(A[it] + d, B[it] + d, P[*nt]);
			ans[it] += F1.get(M-1) - F1.get(*nt) - (F2.get(M-1) - F2.get(*nt)) * (B[it] - A[it]);
		}
		*/
	}
	for(int i=1; i<=N; i++) printf("%lld\n", ans[i]);
	return 0;
}

Compilation message (stderr)

walls.cpp: In function 'int main()':
walls.cpp:95:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |   while(k+1 < E.size() && max(P[E[k+1]] - P[E[k]], P[E[k]] - P[E[k+1]]) <= B[it] - A[it]) ++k;
      |         ~~~~^~~~~~~~~~
walls.cpp: In function 'int dst(int, int, int)':
walls.cpp:29:1: warning: control reaches end of non-void function [-Wreturn-type]
   29 | }
      | ^
walls.cpp: In function 'int main()':
walls.cpp:33:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |  scanf("%d%d", &N, &M);
      |  ~~~~~^~~~~~~~~~~~~~~~
walls.cpp:35:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |   scanf("%d%d", &A[i], &B[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
walls.cpp:41:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |   int x; scanf("%d", &x);
      |          ~~~~~^~~~~~~~~~

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