oj.uz

Submission #9833

# Submission time Handle Problem Language Result Execution time Memory
9833 2014-09-30T08:41:58 Z Qwaz 허수아비 (JOI14_scarecrows) C++
100 / 100
 720 ms 93272 KB 
#include <cstdio>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;
const int MAX = 200020;
typedef long long ll;

struct point {
	int x, y, index;
};

bool compareX(const point &p, const point &q){
	return p.x < q.x;
}

int n;
point data[MAX];

void input(){
	scanf("%d", &n);

	int i;
	for(i = 0; i<n; i++)
		scanf("%d%d", &data[i].x, &data[i].y);

	sort(data, data+n, compareX);
	for(i = 0; i<n; i++)
		data[i].index = i;
}

ll ans;
set < int > st;

void solve(int s, int e){
	if(s+1 >= e)
		return;

	int i, j, m = (s+e) >> 1;
	vector < int > minYList;

	//x, y가 자신보다 작으면서 y가 최대로 큰 허수아비를 찾는다
	st.clear();
	for(i = m; i<e; i++){
		set < int >::iterator it;
		it = st.lower_bound(data[i].y);

		if(it == st.begin()) minYList.push_back(-1);
		else {
			it--;
			minYList.push_back(*it);
		}

		st.insert(data[i].y);
	}

	solve(s, m);
	solve(m, e);

	point stack[MAX];
	int top;

	j = s;
	top = 0;
	for(i = m; i<e; i++){
		while(j < m && data[j].y < data[i].y){
			while(top && data[j].x > stack[top-1].x)
				top--;
			stack[top++] = data[j++];
		}

		int minY = minYList[data[i].index-m];
		
		int p = 0, q = top, r;
		while(p < q){
			r = (p+q) >> 1;
			if(stack[r].y > minY)
				q = r;
			else
				p = r+1;
		}

		ans += top-p;
	}

	i = s;
	j = m;

	//Merge
	point list[MAX];
	int lFull = 0;
	while(1){
		if(i == m && j == e) break;

		if((i < m && data[i].y < data[j].y) || j == e)
			list[lFull++] = data[i++];
		else
			list[lFull++] = data[j++];
	}

	for(i = s; i<e; i++)
		data[i] = list[i-s];
}

int main(){
	input();

	solve(0, n);

	printf("%lld\n", ans);

	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 45624 KB Output is correct
2 Correct 0 ms 45628 KB Output is correct
3 Correct 0 ms 45620 KB Output is correct
4 Correct 0 ms 45628 KB Output is correct
5 Correct 0 ms 45628 KB Output is correct
6 Correct 0 ms 45624 KB Output is correct
7 Correct 0 ms 45624 KB Output is correct
8 Correct 0 ms 45628 KB Output is correct
9 Correct 0 ms 45624 KB Output is correct
10 Correct 0 ms 40932 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 64504 KB Output is correct
2 Correct 12 ms 64500 KB Output is correct
3 Correct 8 ms 64492 KB Output is correct
4 Correct 4 ms 64492 KB Output is correct
5 Correct 4 ms 64488 KB Output is correct
6 Correct 4 ms 64504 KB Output is correct
7 Correct 12 ms 64504 KB Output is correct
8 Correct 8 ms 64500 KB Output is correct
9 Correct 4 ms 64504 KB Output is correct
10 Correct 8 ms 64500 KB Output is correct
11 Correct 12 ms 64508 KB Output is correct
12 Correct 8 ms 64376 KB Output is correct

Subtask #3
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 428 ms 90900 KB Output is correct
2 Correct 712 ms 93260 KB Output is correct
3 Correct 504 ms 90908 KB Output is correct
4 Correct 456 ms 90908 KB Output is correct
5 Correct 508 ms 90912 KB Output is correct
6 Correct 584 ms 91640 KB Output is correct
7 Correct 660 ms 92356 KB Output is correct
8 Correct 700 ms 93172 KB Output is correct
9 Correct 428 ms 90900 KB Output is correct
10 Correct 544 ms 90904 KB Output is correct
11 Correct 612 ms 90908 KB Output is correct
12 Correct 668 ms 93272 KB Output is correct
13 Correct 704 ms 93268 KB Output is correct
14 Correct 388 ms 90904 KB Output is correct
15 Correct 604 ms 90912 KB Output is correct
16 Correct 720 ms 93268 KB Output is correct
17 Correct 392 ms 85692 KB Output is correct
18 Correct 676 ms 92344 KB Output is correct
19 Correct 656 ms 90912 KB Output is correct
20 Correct 664 ms 90912 KB Output is correct