Submission #9836

#	Time	Username	Problem	Language	Result	Execution time	Memory
9836		Qwaz	허수아비 (JOI14_scarecrows)	C++98	100 / 100	204 ms	7336 KiB

scarecrows

#include <cstdio>
#include <algorithm>

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

struct point {
	int x, y;

	bool operator < (const point &t) const {
		return x < t.x;
	}
};

int n;
point data[MAX], tmp[MAX];

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

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

point lStack[MAX], rStack[MAX];
int lTop, rTop;

ll solve(int s, int e){
	if(s >= e-1)
		return 0;

	int m = (s+e)>>1;

	ll ans = 0;
	ans += solve(s, m);
	ans += solve(m, e);

	lTop = rTop = 0;

	int r, l = s;
	for(r = m; r<e; r++){
		while(l < m && data[l].y < data[r].y){
			while(lTop && lStack[lTop-1].x < data[l].x)
				lTop--;
			lStack[lTop++] = data[l++];
		}

		int minY;
		while(rTop && rStack[rTop-1].x > data[r].x)
			rTop--;
		minY = rTop ? rStack[rTop-1].y : -1;
		rStack[rTop++] = data[r];

		int p = 0, q = lTop, r;
		while(p < q){
			r = (p+q) >> 1;
			if(lStack[r].y > minY)
				q = r;
			else
				p = r+1;
		}

		ans += lTop-p;
	}

	int tFull = 0;
	l = s;
	r = m;
	while(1){
		if(l == m && r == e)
			break;

		if((l < m && data[l].y < data[r].y) || r == e)
			tmp[tFull++] = data[l++];
		else
			tmp[tFull++] = data[r++];
	}

	int i;
	for(i = 0; i<tFull; i++)
		data[s+i] = tmp[i];

	return ans;
}

int main(){
	init();

	printf("%lld\n", solve(0, n));

	return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 85 / 85