Submission #916654

#	Time	Username	Problem	Language	Result	Execution time	Memory
916654		mickey080929	방벽 (JOI15_walls)	C++17	0 / 100	283 ms	30868 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 (!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;
			auto zit = next(yit);
			ll z = -1;
			if (zit != s.end()) z = *zit;

			cur -= abs(b[x] - b[y]);
			if (z != -1) cur -= abs(b[y] - b[z]);
			s.erase(yit);
			if (z == -1) continue;
			if (b[x] > b[y]) {
				if (b[x] > b[z]) {
					auto wit = next(zit);
					s.erase(zit);
					if (wit == s.end()) continue;
					cur += b[x] - b[z];
					pq.push({b[*wit] - b[x], x, *wit});
				}
				else {
					if (xit == s.begin()) {
						s.erase(xit);
						continue;
					}
					cur += b[z] - b[x];
					auto wit = prev(xit);
					s.erase(xit);
					pq.push({b[*wit] - b[z], *wit, z});
				}
			}
			else {
				if (b[x] < b[z]) {
					auto wit = next(zit);
					s.erase(zit);
					if (wit == s.end()) continue;
					cur += b[z] - b[x];
					pq.push({b[x] - b[*wit], x, *wit});
				}
				else {
					if (xit == s.begin()) {
						s.erase(xit);
						continue;
					}
					cur += b[x] - b[z];
					auto wit = prev(xit);
					s.erase(xit);
					pq.push({b[z] - b[*wit], *wit, z});
				}
			}
		}
		if (s.size() == 1) {
			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: 0 / 10
• Subtask 2: 0 / 45
• Subtask 3: 0 / 45