oj.uz

Submission #131797

# Submission time Handle Problem Language Result Execution time Memory
131797 2019-07-17T16:14:41 Z anayk Sails (IOI07_sails) C++14
25 / 100
 251 ms 5276 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;

	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;

	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);

		// for(int j = 0; j < h; j++)
		// 	std::cout << val(j) << " ";
		// std::cout << "ends: " << l << " " << r;
		// std::cout << std::endl;
	}

	long long answer = 0;
	for(int i = 0; i < h; i++)
	{
		long long cur = (long long) val(i);
		//std::cout << cur << std::endl;
		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 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 1276 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 62 ms 1704 KB Output isn't correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 116 ms 2828 KB Output isn't correct

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 194 ms 4888 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 218 ms 5184 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 251 ms 5276 KB Output isn't correct
2 Halted 0 ms 0 KB -