Submission #1264115

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264115		kunzaZa183	Sails (IOI07_sails)	C++20	100 / 100	199 ms	5900 KiB

sails

#include <bits/stdc++.h>
using namespace std;
vector<int> mini, maxi, lz;
int ss;
void lzy(int curin, int curl, int curr) {
	if (curl == curr) {
		maxi[curin] += lz[curin];
		mini[curin] += lz[curin];
		lz[curin] = 0;
		return;
	}

	lz[curin * 2 + 1] += lz[curin];
	lz[curin * 2 + 2] += lz[curin];

	maxi[curin] += lz[curin];
	mini[curin] += lz[curin];
	lz[curin] = 0;
}
int ql, qr;
void upd(int curin, int curl, int curr) {
	lzy(curin, curl, curr);

	if (ql > curr || qr < curl)
		return;

	if (ql <= curl && curr <= qr) {
		lz[curin] = 1;
		return lzy(curin, curl, curr);
	}

	upd(curin * 2 + 1, curl, (curl + curr) / 2);
	upd(curin * 2 + 2, (curl + curr) / 2 + 1, curr);
	maxi[curin] = max(maxi[curin * 2 + 1], maxi[curin * 2 + 2]);
	mini[curin] = min(mini[curin * 2 + 1], mini[curin * 2 + 2]);
}
int qval;
int lmost(int curin, int curl, int curr) {
	lzy(curin, curl, curr);

	if (curl == curr)
		return curl;

	lzy(curin * 2 + 1, curl, (curl + curr) / 2);
	lzy(curin * 2 + 2, (curl + curr) / 2 + 1, curr);
	if (mini[curin * 2 + 1] <= qval && qval <= maxi[curin * 2 + 1]) {
		return lmost(curin * 2 + 1, curl, (curl + curr) / 2);
	}
	assert(mini[curin * 2 + 2] <= qval && qval <= maxi[curin * 2 + 2]);
	return lmost(curin * 2 + 2, (curl + curr) / 2 + 1, curr);
}
int rmost(int curin, int curl, int curr) {
	lzy(curin, curl, curr);

	if (curl == curr)
		return curl;

	lzy(curin * 2 + 1, curl, (curl + curr) / 2);
	lzy(curin * 2 + 2, (curl + curr) / 2 + 1, curr);
	if (mini[curin * 2 + 2] <= qval && qval <= maxi[curin * 2 + 2])
		return rmost(curin * 2 + 2, (curl + curr) / 2 + 1, curr);
	return rmost(curin * 2 + 1, curl, (curl + curr) / 2);
}
int qin;
int qry(int curin, int curl, int curr) {
	lzy(curin, curl, curr);

	if (curl == curr) {
		return maxi[curin];
	}

	int mid = (curl + curr) / 2;
	if (qin <= mid)
		return qry(curin * 2 + 1, curl, mid);
	return qry(curin * 2 + 2, mid + 1, curr);
}
int main() {
	int n;
	cin >> n;
	vector<pair<int, int>> vpii(n);
	for (auto& [a, b] : vpii)
		cin >> a >> b;

	sort(vpii.begin(), vpii.end());

	ss = vpii.back().first;
	mini = maxi = lz = vector<int>(4 * ss);

	for (auto [height, amt] : vpii) {
		int l = height - amt;

		qin = l;
		int val = qry(0, 0, ss - 1);

		qval = val;
		int ll = lmost(0, 0, ss - 1), rr = min(height - 1, rmost(0, 0, ss - 1));

		if (rr == height - 1) {
			ql = ll, qr = ll + amt - 1;
			upd(0, 0, ss - 1);
		}
		else {
			ql = rr + 1, qr = height - 1;
			upd(0, 0, ss - 1);

			int k = amt - (qr - ql + 1);
			ql = ll, qr = ql + k - 1;
			upd(0, 0, ss - 1);
		}
	}

	long long ans = 0;
	for (int i = 0; i < ss; i++) {
		qin = i;
		long long smth = qry(0, 0, ss - 1);
		ans += smth * (smth - 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