oj.uz

답안 #5979

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
5979 2014-06-08T12:03:50 Z model_code 허수아비 (JOI14_scarecrows) C++
100 / 100
 2972 ms 29752 KB 
#include<cstdio>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < n; ++i)
using namespace std;
typedef pair<int,int> P;
typedef long long ll;

const int MX = 200005, INF = 2000020000;

ll ans;
P in[MX];

struct bit {
	vector<int> d;
	bit(int n):d(n+5,0){}
	void add(int i){ while(i < d.size()) ++d[i], i += i&-i;}
	int sum(int i){ int res = 0; while(i) res += d[i], i -= i&-i; return res;}
};

void f(P p[], int n){
	if(n <= 1) return;
	int c = n/2;
	f(p,c); f(p+c,n-c);
	set<int> s;
	vector<P> l, r; // cover range
	
	s.insert(INF);
	for(int i = c-1; i >= 0; --i){
		int x = *(s.lower_bound(p[i].se));
		l.push_back(P(p[i].se,x-1));
		s.insert(p[i].se);
	}
	s.clear(); s.insert(INF);
	for(int i = c; i < n; ++i){
		int x = -(*(s.lower_bound(-p[i].se)));
		r.push_back(P(x+1,p[i].se));
		s.insert(-p[i].se);
	}
	sort(l.begin(),l.end());
	sort(r.begin(),r.end());
	
	map<int,int> z; // compress axis
	rep(i,l.size()){
		z.insert(P(l[i].fi,0));
		z.insert(P(l[i].se,0));
	}
	rep(i,r.size()){
		z.insert(P(r[i].fi,0));
		z.insert(P(r[i].se,0));
	}
	int k = 1;
	for(map<int,int>::iterator it = z.begin(); it != z.end(); ++it) it->se = k++;
	
	bit d(k);
	
	// valid pair : R.first <= L.first <= R.second <= L.second
	k = 0;
	rep(i,l.size()){
		while(k < r.size() && r[k].fi <= l[i].fi) d.add(z[r[k++].se]);
		ans += d.sum(z[l[i].se])-d.sum(z[l[i].fi]-1);
	}
}

int main(){
	int n;
	scanf("%d",&n);
	rep(i,n) scanf("%d%d",&in[i].fi,&in[i].se);
	sort(in,in+n);
	
	f(in,n);
	
	printf("%lld\n",ans);
	
	return 0;
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2808 KB Output is correct
2 Correct 0 ms 2808 KB Output is correct
3 Correct 0 ms 2808 KB Output is correct
4 Correct 0 ms 2808 KB Output is correct
5 Correct 0 ms 2808 KB Output is correct
6 Correct 4 ms 2808 KB Output is correct
7 Correct 0 ms 2808 KB Output is correct
8 Correct 0 ms 2808 KB Output is correct
9 Correct 0 ms 2808 KB Output is correct
10 Correct 0 ms 2808 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 3212 KB Output is correct
2 Correct 44 ms 3368 KB Output is correct
3 Correct 40 ms 3276 KB Output is correct
4 Correct 28 ms 3428 KB Output is correct
5 Correct 40 ms 3352 KB Output is correct
6 Correct 44 ms 3348 KB Output is correct
7 Correct 40 ms 3368 KB Output is correct
8 Correct 28 ms 3212 KB Output is correct
9 Correct 36 ms 3212 KB Output is correct
10 Correct 36 ms 3352 KB Output is correct
11 Correct 40 ms 3268 KB Output is correct
12 Correct 28 ms 3148 KB Output is correct

Subtask #3
85.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2192 ms 19696 KB Output is correct
2 Correct 2940 ms 24780 KB Output is correct
3 Correct 2568 ms 24728 KB Output is correct
4 Correct 2396 ms 29752 KB Output is correct
5 Correct 2684 ms 27316 KB Output is correct
6 Correct 2760 ms 25292 KB Output is correct
7 Correct 2892 ms 24840 KB Output is correct
8 Correct 2972 ms 24748 KB Output is correct
9 Correct 2208 ms 19696 KB Output is correct
10 Correct 2252 ms 22132 KB Output is correct
11 Correct 2420 ms 24096 KB Output is correct
12 Correct 2716 ms 24516 KB Output is correct
13 Correct 2880 ms 24656 KB Output is correct
14 Correct 2036 ms 20272 KB Output is correct
15 Correct 2460 ms 24084 KB Output is correct
16 Correct 2904 ms 24656 KB Output is correct
17 Correct 1708 ms 16832 KB Output is correct
18 Correct 2904 ms 24704 KB Output is correct
19 Correct 2856 ms 24660 KB Output is correct
20 Correct 2864 ms 24740 KB Output is correct