Submission #983357

#	Time	Username	Problem	Language	Result	Execution time	Memory
983357		michified	Sails (IOI07_sails)	C++17	100 / 100	40 ms	5716 KiB

sails

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

struct mast_t {
	ll cnt, h;
};

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	ll n, i, l, r, tmp;
	cin >> n;
	vector<mast_t> masts(n);
	for (i = 0; i < n; i++) cin >> masts[i].h >> masts[i].cnt;
	sort(masts.begin(), masts.end(), [](const mast_t& one, const mast_t& two){return one.h < two.h;});
	map<ll, ll> histo;
	mast_t mast;
	histo[0]++;
	histo[masts[0].cnt]--;
	for (i = 1; i < n; i++) {
		mast = masts[i];
		l = mast.h - mast.cnt;
		r = mast.h;
		histo[r]--;
		if (histo.find(l) != histo.end()) {
			histo[l]++;
			if (histo[l] == 0) histo.erase(l);
			continue;
		}
		auto lo = prev(histo.lower_bound(l)), hi = histo.upper_bound(l);
		lo -> second++;
		histo[lo -> first - l + hi -> first]--;
		if (lo -> second == 0) histo.erase(lo);
		hi -> second++;
		if (hi -> second == 0) histo.erase(hi);
	}
	auto cur = histo.begin();
	ll ans = 0, count = cur -> second;
	while (count > 0) {
		ans += count * (count - 1) * (next(cur) -> first - cur -> first);
		count += next(cur) -> second;
		cur = next(cur);
	}
	cout << ans / 2;
	return 0;
}

Compilation message (stderr)

sails.cpp: In function 'int main()':
sails.cpp:13:17: warning: unused variable 'tmp' [-Wunused-variable]
   13 |  ll n, i, l, r, tmp;
      |                 ^~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 5 / 5
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10
• Subtask 11: 10 / 10