oj.uz

Submission #9832

# Submission time Handle Problem Language Result Execution time Memory
9832 2014-09-30T08:40:45 Z Qwaz 허수아비 (JOI14_scarecrows) C++
15 / 100
 440 ms 90900 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("%d\n", ans);

	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 45628 KB Output is correct
2 Correct 0 ms 45624 KB Output is correct
3 Correct 0 ms 45624 KB Output is correct
4 Correct 0 ms 45628 KB Output is correct
5 Correct 0 ms 45624 KB Output is correct
6 Correct 0 ms 45628 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 45628 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 0 ms 64500 KB Output is correct
2 Correct 8 ms 64504 KB Output is correct
3 Correct 8 ms 64492 KB Output is correct
4 Correct 8 ms 64496 KB Output is correct
5 Correct 8 ms 64492 KB Output is correct
6 Correct 4 ms 64504 KB Output is correct
7 Correct 12 ms 64500 KB Output is correct
8 Correct 8 ms 64504 KB Output is correct
9 Correct 8 ms 64504 KB Output is correct
10 Correct 4 ms 64508 KB Output is correct
11 Correct 8 ms 64504 KB Output is correct
12 Correct 8 ms 64380 KB Output is correct

Subtask #3
0.0 / 85.0

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