oj.uz

Submission #9834

# Submission time Handle Problem Language Result Execution time Memory
9834 2014-09-30T08:57:02 Z Qwaz 허수아비 (JOI14_scarecrows) C++14
100 / 100
 712 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 45620 KB Output is correct
2 Correct 0 ms 45624 KB Output is correct
3 Correct 0 ms 45620 KB Output is correct
4 Correct 0 ms 45624 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 40936 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 4 ms 64504 KB Output is correct
3 Correct 8 ms 64496 KB Output is correct
4 Correct 8 ms 64496 KB Output is correct
5 Correct 8 ms 64492 KB Output is correct
6 Correct 8 ms 64504 KB Output is correct
7 Correct 8 ms 64504 KB Output is correct
8 Correct 8 ms 64504 KB Output is correct
9 Correct 8 ms 64508 KB Output is correct
10 Correct 4 ms 64508 KB Output is correct
11 Correct 12 ms 64508 KB Output is correct
12 Correct 8 ms 64372 KB Output is correct

Subtask #3
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 432 ms 90900 KB Output is correct
2 Correct 708 ms 93264 KB Output is correct
3 Correct 508 ms 90908 KB Output is correct
4 Correct 456 ms 90908 KB Output is correct
5 Correct 516 ms 90908 KB Output is correct
6 Correct 580 ms 91640 KB Output is correct
7 Correct 664 ms 92348 KB Output is correct
8 Correct 704 ms 93180 KB Output is correct
9 Correct 428 ms 90904 KB Output is correct
10 Correct 532 ms 90904 KB Output is correct
11 Correct 608 ms 90912 KB Output is correct
12 Correct 652 ms 93268 KB Output is correct
13 Correct 712 ms 93268 KB Output is correct
14 Correct 412 ms 90900 KB Output is correct
15 Correct 600 ms 90908 KB Output is correct
16 Correct 712 ms 93272 KB Output is correct
17 Correct 376 ms 85692 KB Output is correct
18 Correct 672 ms 92344 KB Output is correct
19 Correct 676 ms 90912 KB Output is correct
20 Correct 672 ms 90912 KB Output is correct