Submission #1278591

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278591		sssamui	Sails (IOI07_sails)	C++20	100 / 100	657 ms	7384 KiB

sails

#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
using ll = long long;

const int sz = 1 << 17;
const int MXN = 1e5;

struct node
{
	ll lz = 0;
	ll sum = 0;
	ll tsum = 0;
};

vector<node> tree(2 * sz);

void pushup(int node)
{
	int lc = 2 * node, rc = 2 * node + 1;
	tree[node].sum = tree[lc].sum + tree[rc].sum, tree[node].tsum = tree[lc].tsum + tree[rc].tsum;
}

void pushdown(int node, int l, int r)
{
	int mid = l + (r - l) / 2;
	ll clz = tree[node].lz;
	tree[node].lz = 0;
	ll tsumsub = clz * (clz + 1) / 2;
	int lc = 2 * node, rc = 2 * node + 1;
	ll lnum = 1ll * (mid - l + 1), rnum = 1ll * (r - mid);

	tree[lc].tsum += (clz * tree[lc].sum + tsumsub * lnum), tree[rc].tsum += (clz * tree[rc].sum + tsumsub * rnum);
	tree[lc].sum += clz * lnum, tree[rc].sum += clz * rnum;
	tree[lc].lz += clz, tree[rc].lz += clz;
}

void upd(int node, int l, int r, int a, int b)
{
	if ((r < a) || (l > b)) return;
	if ((a <= l) && (r <= b))
	{
		tree[node].lz++;
		tree[node].sum += 1ll * (r - l + 1);
		tree[node].tsum += tree[node].sum;
		return;
	}

	pushdown(node, l, r);
	int mid = l + (r - l) / 2;
	int lc = 2 * node, rc = 2 * node + 1;
	upd(lc, l, mid, a, b), upd(rc, mid + 1, r, a, b);
	pushup(node);
}

ll rq(int node, int l, int r, int a, int b)
{
	if ((r < a) || (l > b)) return 0;
	if ((a <= l) && (r <= b)) return tree[node].tsum;
	pushdown(node, l, r);
	int mid = l + (r - l) / 2;
	int lc = 2 * node, rc = 2 * node + 1;
	return rq(lc, l, mid, a, b) + rq(rc, mid + 1, r, a, b);
}

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

	int n;
	cin >> n;
	vector<pair<int, int>> sails(n);
	for (int i = 0; i < n; i++) cin >> sails[i].first >> sails[i].second;
	sort(sails.begin(), sails.end());

	for (pair<int, int> sail : sails)
	{
		int h = sail.first, k = sail.second;
		ll lownum = rq(1, 0, MXN, h - k, h - k);
		int cl = 0, cr = h - k;
		while (cl < cr)
		{
			int mid = cl + (cr - cl) / 2;
			if (rq(1, 0, MXN, mid, mid) > lownum) cl = mid + 1;
			else cr = mid;
		}

		int fl = h - k, fr = h - 1;
		while (fl < fr)
		{
			int mid = fl + (fr - fl + 1) / 2;
			if (rq(1, 0, MXN, mid, mid) < lownum) fr = mid - 1;
			else fl = mid;
		}

		int numlowadd = fl - (h - k) + 1;
		upd(1, 0, MXN, cl, cl + numlowadd - 1), upd(1, 0, MXN, fl + 1, h - 1);
	}

	cout << tree[1].tsum - tree[1].sum;
}

• 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