Submission #9835

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
9835	2014-09-30T10:20:44 Z	Qwaz	허수아비 (JOI14_scarecrows)	C++	Compilation error	0 ms	0 KB

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){
		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;
}

Compilation message

In file included from /usr/include/c++/4.6/algorithm:63:0,
                 from scarecrows.cpp:2:
/usr/include/c++/4.6/bits/stl_algo.h: In function '_RandomAccessIterator std::__unguarded_partition(_RandomAccessIterator, _RandomAccessIterator, const _Tp&) [with _RandomAccessIterator = point*, _Tp = point]':
/usr/include/c++/4.6/bits/stl_algo.h:2253:70:   instantiated from '_RandomAccessIterator std::__unguarded_partition_pivot(_RandomAccessIterator, _RandomAccessIterator) [with _RandomAccessIterator = point*]'
/usr/include/c++/4.6/bits/stl_algo.h:2284:54:   instantiated from 'void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size) [with _RandomAccessIterator = point*, _Size = long int]'
/usr/include/c++/4.6/bits/stl_algo.h:5407:4:   instantiated from 'void std::sort(_RAIter, _RAIter) [with _RAIter = point*]'
scarecrows.cpp:25:19:   instantiated from here
/usr/include/c++/4.6/bits/stl_algo.h:2215:4: error: passing 'const point' as 'this' argument of 'bool point::operator<(const point&)' discards qualifiers [-fpermissive]
scarecrows.cpp: In function 'void init()':
scarecrows.cpp:20:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scarecrows.cpp:24:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]