第二回ドワンゴからの挑戦状本選

出てました。C,Dに手が出ず終了。

コンテスト中
A:流石にやるだけだと思ったんだけど案外みんな引っかかったらしい.微妙にsemiexpさんに負けた.
B:やるだけ.普通にsem(ry
C:個人的にはかなり難しかった.O(N^2)は思いついたので(各区間に対しどの高さの点が入るかは前計算とかいろいろすれば求まる)書いたが,バグが取れず終了
D:ふええ
ちゃんと難しい問題も解かないとダメだということが分かった(当たり前だよなあ?)

コンテスト後
CはちゃんとJOIやってればいつものって感じなようだ(確かに言われてみれば簡単だし,平面走査もほとんどやることがない).精進が足りない.
Dはまだ把握してません.
でもCの発想部分なかなかおもしろいなあ(そもそもLISを知らなさすぎてコンテスト中は平面上の点という気持ちにすらならなかった)
あとCで重要なのは,細かい+-1とかを考えるのは（◞‸◟）なので,まず左下と右上に点を追加しておく,というのと,奇数の点の個数は与えられたやつを2でわったものを書いた時の面積と同じだということに気づくことですね.

2日後くらい
PCの電源コードが見当たらず連絡したら忘れていたらしく郵送していただいた.申し訳NASA.ありがとうございました.

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
typedef long long ll;
const int MAXN=252527;
int N,W,H,x[MAXN],y[MAXN],l[MAXN],r[MAXN];
vector<int> ash;
struct segtree{
	static const int N=1<<18;
	int seg[N*2];
	void init(){
		rep(i,N*2) seg[i]=0;
	}
	void update(int x,int v){
		x+=N;
		seg[x]=v;
		x/=2;
		while(x){
			seg[x]=max(seg[x*2],seg[x*2+1]);
			x/=2;
		}
	}
	int getmax(int a,int b,int l=0,int r=N,int k=1){
		if(b<=l||r<=a) return 0;
		if(a<=l&&r<=b) return seg[k];
		return max(getmax(a,b,l,(l+r)/2,k*2),getmax(a,b,(l+r)/2,r,k*2+1));
	}
}seg;
void calcl(){
	seg.init();
	rep(i,N){
		l[i]=seg.getmax(0,y[i])+1;
		seg.update(y[i],l[i]);
	}

}
void calcr(){
	seg.init();
	for(int i=N-1;i>=0;i--){
		r[i]=seg.getmax(y[i]+1,segtree::N)+1;
		seg.update(y[i],r[i]);
	}
}
typedef pair<int,int> P;
vector<int> vc[MAXN];
ll calc(int id){
	vector<P> es;
	for(int i:vc[id]) es.pb(P(i,0));
	for(int i:vc[id+1]) es.pb(P(i,1));
	int U=y[vc[id+1][0]];
	int D=-1;
	int L=-1;
	int it=0;
	ll ret=0;
	sort(all(es));
	for(P p:es){
		int i=p.fs,type=p.sc;
		if(D>=0) ret+=(ll)max(ash[U]-ash[D],0)*(x[i]-x[L]);
		if(type==0) D=y[i];
		else{
			it++;
			if(it<vc[id+1].size()) U=y[vc[id+1][it]];
		}
		L=i;
	}
	return ret;
}
int main(){
	cin>>N>>W>>H;
	rep1(i,N) cin>>x[i]>>y[i];
	x[N+1]=W,y[N+1]=H;
	N+=2;
	rep(i,N) x[i]/=2,y[i]/=2;
	rep(i,N) ash.pb(y[i]);
	sort(all(ash));
	rep(i,N) y[i]=lower_bound(all(ash),y[i])-ash.begin();
	calcl();
	calcr();
	int LIS=l[N-1];
	rep(i,N){
		if(l[i]+r[i]!=LIS+1) continue;
		vc[l[i]-1].pb(i);
	}
	ll ans=0;
	rep(i,LIS-1) ans+=calc(i);
	cout<<ans<<endl;
}