Submission #9834

#	Time	Username	Problem	Language	Result	Execution time	Memory
9834		Qwaz	허수아비 (JOI14_scarecrows)	C++14	100 / 100	712 ms	93272 KiB

scarecrows

#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 / 5
• Subtask 2: 10 / 10
• Subtask 3: 85 / 85