oj.uz

Submission #131800

# Submission time Handle Problem Language Result Execution time Memory
131800 2019-07-17T16:24:42 Z anayk Sails (IOI07_sails) C++14
100 / 100
 272 ms 4944 KB 
#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.0 / 5.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 376 KB Output is correct
2 Correct 19 ms 3448 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1016 KB Output is correct
2 Correct 60 ms 1120 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 1292 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 2216 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 4020 KB Output is correct
2 Correct 194 ms 4944 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 4172 KB Output is correct
2 Correct 148 ms 4856 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 4216 KB Output is correct
2 Correct 187 ms 2960 KB Output is correct