Submission #881535

#	Time	Username	Problem	Language	Result	Execution time	Memory
881535		rxlfd314	Sails (IOI07_sails)	C++17	100 / 100	77 ms	4624 KiB

sails

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
#define cerr if (false) cout
constexpr int mxN = 100005;
int N, fen[mxN];
ari2 poles[mxN];
set<ari2> ranges;
void upd(int i, int v) {
	for (; i < mxN; i += i & -i) {
		fen[i] += v;
	}
}
int qry(int i) {
	int ret = 0;
	for (; i > 0; i -= i & -i) {
		ret += fen[i];
	}
	return ret;
}
signed main() {
#ifdef cerr
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
#endif
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> poles[i][0] >> poles[i][1];
	}	
	sort(poles, poles + N);
	ranges.insert({1, 0});
	for (int i = 0; i < N; i++) {
		auto back = --ranges.end();
		if (qry((*back)[1]) == 0 && poles[i][0] > (*back)[1]) {
			ranges.erase(back);
			ranges.insert({(*back)[0], poles[i][0]});
		} else if (poles[i][0] > (*back)[1]) {
			ranges.insert({(*back)[1] + 1, poles[i][0]});
		}
		auto nrst = ranges.lower_bound(ari2{poles[i][0] - poles[i][1] + 1, -1});
		if (nrst != ranges.end()) {
			upd((*nrst)[0], 1);
			upd((*--ranges.end())[1] + 1, -1);
		}
		if (nrst == ranges.end() || (*nrst)[0] > poles[i][0] - poles[i][1] + 1) {
			auto behind = prev(nrst);
			poles[i][1] -= nrst == ranges.end() ? 0 : poles[i][0] - (*nrst)[0] + 1;
			upd((*behind)[0], 1);
			upd((*behind)[0] + poles[i][1], -1);
			ari2 v = *behind;
			ranges.erase(behind);
			ranges.insert({v[0], v[0] + poles[i][1] - 1});
			ranges.insert({v[0] + poles[i][1], v[1]});
			if (nrst != ranges.end() && qry(v[1]) == qry((*nrst)[0])) {
				ranges.erase(ranges.find({v[0] + poles[i][1], v[1]}));
				ranges.erase(nrst);
				ranges.insert({v[0] + poles[i][1], (*nrst)[1]});
			}
			behind = ranges.find({v[0], v[0] + poles[i][1] - 1});
			if (behind != ranges.begin()) {
				auto behind2 = prev(behind);
				if (qry((*behind2)[1]) == qry(v[0])) {
					ari2 l = *behind2, r = *behind;
					ranges.erase(behind);
					ranges.erase(behind2);
					ranges.insert({l[0], r[1]});
				}
			}
		} else if (nrst != ranges.end() && nrst != ranges.begin()) {
			auto behind = prev(nrst);
			if (qry((*behind)[0]) == qry((*nrst)[0])) {
				ari2 l = *behind, r = *nrst;
				ranges.erase(behind);
				ranges.erase(nrst);
				ranges.insert({l[0], r[1]});
			}
		}
	}
	ll ans = 0;
	for (int i = 1; i < mxN; i++) {
		ll v = qry(i);
		ans += v * (v - 1) / 2;
	}
	cout << ans << '\n';
}

• 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