Submission #131800

#	Time	Username	Problem	Language	Result	Execution time	Memory
131800		anayk	Sails (IOI07_sails)	C++14	100 / 100	272 ms	4944 KiB

sails

#include <iostream>
#include <algorithm>

#define MAXH 100005

int h;
int seg[4*MAXH];
int min[4*MAXH];
int max[4*MAXH];

void shift(int id)
{
	seg[2*id] += seg[id];
	seg[2*id+1] += seg[id];

	min[2*id] += seg[id];
	min[2*id+1] += seg[id];
	max[2*id] += seg[id];
	max[2*id+1] += seg[id];

	seg[id] = 0;
}

int val(int x, int id = 1, int l = 0, int r = h-1)
{
	if(l == r)
		return seg[id];

	shift(id);

	int m = (l+r)/2;
	if(x <= m)
		return val(x, 2*id, l, m);
	else
		return val(x, 2*id+1, m+1, r);
}

void upd(int x, int y, int id = 1, int l = 0, int r = h-1)
{
	if(y < l || r < x)
		return;

	if(x <= l && r <= y)
	{
		seg[id]++;
		min[id]++;
		max[id]++;
		return;
	}

	shift(id);

	int m = (l+r)/2;
	upd(x, y, 2*id, l, m);
	upd(x, y, 2*id+1, m+1, r);

	min[id] = std::min(min[2*id], min[2*id+1]);
	max[id] = std::max(max[2*id], max[2*id+1]);
}

int findR(int x, int id = 1, int l = 0, int r = h-1)
{
	if (l == r)
		return l;

	shift(id);

	int m = (l+r)/2;
	if(min[2*id+1] <= x)
		return findR(x, 2*id+1, m+1, r);
	else
		return findR(x, 2*id, l, m);
}

int findL(int x, int id = 1, int l = 0, int r = h-1)
{
	if (l == r)
		return l;
	
	shift(id);

	int m = (l+r)/2;
	if(max[2*id] >= x)
		return findL(x, 2*id, l, m);
	else
		return findL(x, 2*id+1, m+1, r);
}

int main()
{
	int n;
	std::cin >> n;

	h = 0;
	std::pair<int, int> mast[n];
	for(int i = 0; i < n; i++)
	{
		std::cin >> mast[i].first >> mast[i].second;
		h = std::max(h, mast[i].first);
	}

	std::sort(mast, mast + n);

	for(int i = 0; i < n; i++)
	{
		int x = mast[i].first;
		int y = mast[i].second;

		int a = h-x;
		int last = val(a+y-1);

		int l = findL(last);
		int r = findR(last);

		if(a <= l-1)
			upd(a, l-1);

		int count = a+y-std::max(a, l);
		upd(r-count+1, r);
	}

	long long answer = 0;
	for(int i = 0; i < h; i++)
	{
		long long cur = (long long) val(i);
		answer += cur*(cur-1)/2;
	}

	std::cout << answer << std::endl;

	return 0;
}

• 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