oj.uz

Submission #881535

# Submission time Handle Problem Language Result Execution time Memory
881535 2023-12-01T12:09:04 Z rxlfd314 Sails (IOI07_sails) C++17
100 / 100
 77 ms 4624 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB Output is correct
2 Correct 1 ms 348 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 348 KB Output is correct
2 Correct 2 ms 860 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 604 KB Output is correct
2 Correct 18 ms 984 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 2392 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 1976 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 2460 KB Output is correct
2 Correct 63 ms 2936 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 4624 KB Output is correct
2 Correct 35 ms 2204 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 3428 KB Output is correct
2 Correct 38 ms 2384 KB Output is correct