Submission #916679

#	Time	Username	Problem	Language	Result	Execution time	Memory
916679		mickey080929	방벽 (JOI15_walls)	C++17	100 / 100	317 ms	33572 KiB

walls

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;

const ll inf = 2e18;

struct Wall{
	ll l, r, id;
	bool operator<(const Wall &other) const {
		if (r - l == other.r - other.l) return id < other.id;
		return r - l < other.r - other.l;
	}
};

int main() {
	ios_base :: sync_with_stdio(false); cin.tie(NULL);
	ll n, m;
	cin >> n >> m;
	vector<Wall> a(n);
	vector<ll> b(m);
	for (ll i=0; i<n; i++) {
		cin >> a[i].l >> a[i].r;
		a[i].id = i;
	}
	sort(a.begin(), a.end());
	ll mx = 0, mn = inf;
	for (ll i=0; i<m; i++) {
		cin >> b[i];
		mx = max(mx, b[i]);
		mn = min(mn, b[i]);
	}
	b.erase(unique(b.begin(), b.end()), b.end());
	m = b.size();
	vector<ll> t = {b[0]};
	for (ll i=1; i<m-1; i++) {
		if (b[i-1] > b[i] && b[i] < b[i+1])
			t.push_back(b[i]);
		else if (b[i-1] < b[i] && b[i] > b[i+1])
			t.push_back(b[i]);
	}
	if (m >= 2) t.push_back(b[m-1]);
	m = t.size();
	b = t;
	ll cur = 0;
	set<ll> s;
	priority_queue<array<ll,3>> pq;
	for (ll i=0; i<m; i++) s.insert(i);
	for (ll i=0; i<m-1; i++) {
		pq.push({-abs(b[i+1] - b[i]), i, i+1});
		cur += abs(b[i+1] - b[i]);
	}
	vector<ll> ans(n, 0);
	for (ll i=0; i<n; i++) {
		while (s.size() > 2 && !pq.empty() && -pq.top()[0] < a[i].r - a[i].l) {
			ll x = pq.top()[1];
			ll y = pq.top()[2];
			pq.pop();
			auto xit = s.lower_bound(x);
			if (xit == s.end() || *xit != x) continue;
			auto yit = next(xit);
			if (yit == s.end() || *yit != y) continue;

			cur -= abs(b[x] - b[y]);
			if (xit == s.begin()) {
				s.erase(xit);
				continue;
			}
			if (yit == prev(s.end())) {
				s.erase(yit);
				continue;
			}
			ll z = *prev(xit);
			ll w = *next(yit);
			cur -= abs(b[z] - b[x]);
			cur -= abs(b[y] - b[w]);
			s.erase(xit);
			s.erase(yit);
			cur += abs(b[z] - b[w]);
			pq.push({-abs(b[z] - b[w]), z, w});
		}
		if (mx - mn <= a[i].r - a[i].l) {
			if (a[i].r <= mx) ans[a[i].id] = mx - a[i].r;
			else if (a[i].l >= mn) ans[a[i].id] = a[i].l - mn;
			else ans[a[i].id] = 0;
			continue;
		}
		ll fi = *s.begin();
		ll se = *next(s.begin());
		if (b[fi] < b[se]) {
			if (a[i].l >= b[fi]) {
				ans[a[i].id] = a[i].l - b[fi] + cur - (a[i].r - a[i].l) * ((ll)s.size()-1);
			}
			else {
				ans[a[i].id] = b[se] - a[i].r + cur - (b[se] - b[fi]) - (a[i].r - a[i].l) * ((ll)s.size()-2);
			}
		}
		else {
			if (a[i].r <= b[fi]) {
				ans[a[i].id] = b[fi] - a[i].r + cur - (a[i].r - a[i].l) * ((ll)s.size()-1);
			}
			else {
				ans[a[i].id] = a[i].l - b[se] + cur - (b[fi] - b[se]) - (a[i].r - a[i].l) * ((ll)s.size()-2);
			}
		}
	}
	for (ll i=0; i<n; i++) {
		cout << ans[i] << '\n';
	}
}

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