Submission #1191628

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191628		JooDdae	방벽 (JOI15_walls)	C++20	0 / 100	99 ms	12612 KiB

walls

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

int n, m, l[200200], r[200200];
ll ans[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);
	}

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

	priority_queue<array<int, 2>> pq;
	for(int i=2;i+1<p.size();i++) pq.push({-abs(p[i]-p[i-1]), 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]; });

	ll sum = 0;
	for(int i=2;i+1<p.size();i++) sum += abs(p[i]-p[i-1]);

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

			it = s.erase(s.erase(prev(it)));
			if(prev(it) != s.begin() && next(it) != s.end()) {
				auto C = abs(p[*it] - p[*prev(it)]);
				pq.push({-C, *it});
			}
		}

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

		ans[i] = sum - 1ll*(r[i]-l[i])*(s.size()-3);

		auto it = s.rbegin();
		ans[i] += max(0, abs(p[*it] - p[*next(it)]) - (r[i]-l[i]));
		
		int b = p[*s.begin()], nb = p[*next(s.begin())];
		if(b < nb) {
			if(b < l[i]) ans[i] += l[i]-b, r[i] -= l[i]-b;
			if(r[i] < nb) ans[i] += nb-r[i];
			else ans[i] += r[i]-nb;
		} else {
			if(r[i] < b) ans[i] += b-r[i], l[i] += b-r[i];
			if(nb < l[i]) ans[i] += l[i]-nb;
			else ans[i] += nb-l[i];
		}

	}

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

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