제출 #6003

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
6003		ainta	허수아비 (JOI14_scarecrows)	C++98	100 / 100	192 ms	5776 KiB

scarecrows

#pragma warning(disable:4996)
#include<stdio.h>
#include<algorithm>
using namespace std;
int n;
int st[200010], st2[200010], top, top2;
struct point{
	int x, y;
	bool operator <(const point &p)const{
		return x < p.x;
	}
}w[200010], tw[200010];
void Ins(int num)
{
	while (top && w[st[top]].x < w[num].x)top--;
	st[++top] = num;
}
int Ans(int y)
{
	if (!top || w[st[top]].y < y)return 0;
	int b = 1, e = top, m, res;
	while (b <= e){
		m = (b + e) >> 1;
		if (w[st[m]].y >= y){
			res = m; e = m - 1;
		}
		else b = m + 1;
	}
	return top - res + 1;
}
int Do(int num)
{
	while (top2 && w[st2[top2]].x > w[num].x)top2--;
	st2[++top2] = num;
	if (top2 == 1) return Ans(-1);
	return Ans(w[st2[top2 - 1]].y);
}
long long Gap(int b, int e)
{
	if (b == e)return 0;
	if (e == b + 1){
		if (w[e].y > w[b].y) return 1;
		swap(w[b], w[e]);
		return 0;
	}
	int i, m = (b + e) / 2, pv = b, cnt = b;
	long long res = 0;
	res += Gap(b, m);
	res += Gap(m + 1, e);
	top = 0, top2 = 0;
	for (i = m + 1; i <= e; i++){
		while (pv <= m && w[pv].y < w[i].y){
			Ins(pv);
			tw[cnt++] = w[pv];
			pv++;
		}
		tw[cnt++] = w[i];
		res += Do(i);
	}
	while (pv <= m){
		tw[cnt++] = w[pv];
		pv++;
	}
	for (i = b; i <= e; i++)w[i] = tw[i];
	return res;
}
int main()
{
	int i;
	scanf("%d", &n);
	for (i = 0; i < n; i++){
		scanf("%d%d", &w[i].x, &w[i].y);
	}
	sort(w, w + n);
	printf("%lld\n", Gap(0, n - 1));
}

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