제출 #1192639

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1192639		JooDdae	방벽 (JOI15_walls)	C++20	100 / 100	220 ms	20620 KiB

walls

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, m;
ll ans[200200], l[200200], r[200200];

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m;
	for(int i=1;i<=n;i++) cin >> l[i] >> r[i];

	vector<int> p;
	for(int i=1;i<=m;i++) {
		int x; cin >> x;
		if(!p.empty() && p.back() == x) continue;
		if(p.size() > 1 && (p.rbegin()[1] < p.back()) == (p.back() < x)) p.pop_back();
		p.push_back(x);
	}

	for(int i=1;i<=n;i++) {
		if(p[0] < l[i]) {
			int K = l[i]-p[0];
			l[i] -= K, r[i] -= K, ans[i] += K;
		}
		if(r[i] < p[0]) {
			int K = p[0]-r[i];
			l[i] += K, r[i] += K, ans[i] += K;
		}
	}

	set<int> s;
	for(int i=0;i<p.size();i++) s.insert(i);

	vector<int> id(n); iota(id.begin(), id.end(), 1);
	sort(id.begin(), id.end(), [&](auto a, auto b){ return r[a]-l[a] < r[b]-l[b]; });

	priority_queue<array<int, 2>> pq;
	for(int i=1;i<p.size();i++) pq.push({-abs(p[i]-p[i-1]), i});
	ll sum = 0;
	for(int i=1;i<p.size();i++) sum += abs(p[i]-p[i-1]);

	for(int i : id) {
		while(s.size() > 2 && !pq.empty() && -pq.top()[0] <= r[i]-l[i]) {
			auto [c, u] = pq.top(); pq.pop();
			
			auto it = s.lower_bound(u);
			if(it == s.begin() || it == s.end() || *it != u || abs(p[*it] - p[*prev(it)]) != -c) continue;
			
			if(prev(it) == s.begin()) {
				it = s.erase(prev(it)), sum += c;
			} else if(next(it) == s.end()) {
				it = s.erase(it), sum += c;
			} else {
				it = s.erase(s.erase(prev(it))), sum += c+c;
			}
			
			if(it != s.begin() && it != s.end()) {
				auto C = abs(p[*it] - p[*prev(it)]);
				pq.push({-C, *it});
			}
		}

		if(s.size() <= 3) {
			for(auto x : s) {
				x = p[x];
				if(x < l[i]) {
					ll K = l[i]-x;
					l[i] -= K, r[i] -= K, ans[i] += K;
				} else if(r[i] < x) {
					ll K = x-r[i];
					l[i] += K, r[i] += K, ans[i] += K;
				}
			}
			continue;
		}

		ans[i] += sum - (r[i]-l[i])*(s.size()-1);
		ll b = p[*s.begin()], nb = p[*next(s.begin())];
		ans[i] -= abs(b-nb)-(r[i]-l[i]);
		
		if(b < nb) {
			if(b < l[i]) ans[i] += l[i]-b, r[i] -= l[i]-b;
			ans[i] += nb-r[i];
		} else {
			if(r[i] < b) ans[i] += b-r[i], l[i] += b-r[i];
			ans[i] += l[i]-nb;
		}
	}

	for(int i=1;i<=n;i++) cout << ans[i] << "\n";
}

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