JOI 春合宿 2013 Day2

2時間45分で全完。
取れる問題ちゃんと取れたので良かった

建設事業

平面走査 + segtree + Kruskal + 貪欲
典型盛り合わせみたいな問題で難しいとは感じなかった。

struct edge{
	int from,to;
	ll cost;
	edge(){}
	edge(int from,int to,ll cost):from(from),to(to),cost(cost){}
	bool operator < (const edge& a) const{
		return cost < a.cost;
	}
};
struct event{
	int x,type;
	P l,r; // [l,r]
	event(){}
	event(int x,P l,P r,int type):x(x),l(l),r(r),type(type){}
	bool operator < (const event& a) const{
		if(x!=a.x)return x < a.x;
		return type < a.type;
	}
};
const int SIZE = 1<<20;
struct segtree{
	int seg[SIZE*2],lazy[SIZE*2];
	void lazy_evaluate(int k,int l,int r){
		seg[k]+=lazy[k]*(r-l);
		if(k<SIZE-1){
			lazy[k*2+1]+=lazy[k];
			lazy[k*2+2]+=lazy[k];
		}
		lazy[k]=0;
	}
	void update(int a,int b,int k,int l,int r,int x){
		lazy_evaluate(k,l,r);
		if(r<=a||b<=l)return;
		else if(a<=l&&r<=b){
			lazy[k]+=x;
			lazy_evaluate(k,l,r);
		}else{
			update(a,b,k*2+1,l,(l+r)/2,x);
			update(a,b,k*2+2,(l+r)/2,r,x);
			seg[k]=seg[k*2+1]+seg[k*2+2];
		}
	}
	int query(int a,int b,int k,int l,int r){
		lazy_evaluate(k,l,r);
		if(r<=a||b<=l)return 0;
		else if(a<=l&&r<=b){
			return seg[k];
		}else{
			int lch = query(a,b,k*2+1,l,(l+r)/2);
			int rch = query(a,b,k*2+2,(l+r)/2,r);
			seg[k]=seg[k*2+1]+seg[k*2+2];
			return lch+rch;
		}
	}
	void update(int a,int b,int x){
		update(a,b,0,0,SIZE,x);
	}
	int query(int a,int b){
		return query(a,b,0,0,SIZE);
	}
};
struct UnionFind{
	int par[SIZE],rank[SIZE];
	void init(){
		for(int i=0;i<SIZE;i++){
			par[i]=i;
			rank[i]=0;
		}
	}
	int find(int x){
		if(par[x]==x)return x;
		else return par[x]=find(par[x]);
	}
	void unite(int a,int b){
		a = find(a);
		b = find(b);
		if(a==b)return;
		if(rank[a]<rank[b])par[a]=b;
		else{
			par[b]=a;
			if(rank[a]==rank[b])rank[a]++;
		}
	}
	bool same(int a,int b){
		return find(a)==find(b);
	}
};
int N,M,C;
int X[200100],Y[200100],H[500100];
int p[200100],q[200100],r[200100],s[200100];
ll B[500100];
vector<P> fx[600100],fy[600100];
vector<int> zx,zy;
vector<ll> uc;
vector<edge> es;
vector<event> evx,evy;
segtree seg;
UnionFind uf;
int main(){
	scanf("%d %d %d",&N,&M,&C);
	for(int i=0;i<N;i++){
		scanf("%d %d",&X[i],&Y[i]);
		zx.pb(X[i]);
		zy.pb(Y[i]);
	}
	for(int i=0;i<M;i++){
		scanf("%d %d %d %d",&p[i],&q[i],&r[i],&s[i]);
		zx.pb(p[i]);zx.pb(r[i]);
		zy.pb(q[i]);zy.pb(s[i]);
	}
	for(int i=0;i<C;i++){
		scanf("%lld %d",&B[i],&H[i]);
	}
	sort(all(zx));
	sort(all(zy));
	zx.erase(unique(all(zx)),zx.end());
	zy.erase(unique(all(zy)),zy.end());
	for(int i=0;i<N;i++){
		X[i] = lower_bound(all(zx),X[i])-zx.begin();
		Y[i] = lower_bound(all(zy),Y[i])-zy.begin();
	}
	for(int i=0;i<M;i++){
		p[i] = lower_bound(all(zx),p[i])-zx.begin();
		q[i] = lower_bound(all(zy),q[i])-zy.begin();
		r[i] = lower_bound(all(zx),r[i])-zx.begin();
		s[i] = lower_bound(all(zy),s[i])-zy.begin();
	}
	// | --->
	for(int i=0;i<N;i++){
		fx[X[i]].pb(P(Y[i],i));
	}
	for(int i=0;i<zx.size();i++)sort(all(fx[i]));
	for(int i=0;i<zx.size();i++){
		for(int j=1;j<fx[i].size();j++){
			evx.pb(event(i,fx[i][j-1],fx[i][j],1));
		}
	}
	for(int i=0;i<M;i++){
		evx.pb(event(p[i],P(q[i],-1),P(s[i],-1),0));
		evx.pb(event(r[i],P(q[i],-1),P(s[i],-1),2));
	}
	sort(all(evx));
	for(int i=0;i<evx.size();i++){
		event e = evx[i];
		//printf("%d %d %d %d\n",zx[e.x],zy[e.l.fi],zy[e.r.fi],e.type);
		if(e.type==0){
			seg.update(e.l.fi,e.r.fi+1,1);
		}else if(e.type==1){
			if(seg.query(e.l.fi,e.r.fi+1)==0){
				es.pb(edge(e.l.sec,e.r.sec,zy[e.r.fi]-zy[e.l.fi]));
			}
		}else{
			seg.update(e.l.fi,e.r.fi+1,-1);
		}
	}
	// ----- ^
	for(int i=0;i<N;i++){
		fy[Y[i]].pb(P(X[i],i));
	}
	for(int i=0;i<zy.size();i++)sort(all(fy[i]));
	for(int i=0;i<zy.size();i++){
		for(int j=1;j<fy[i].size();j++){
			evy.pb(event(i,fy[i][j-1],fy[i][j],1));
		}
	}
	for(int i=0;i<M;i++){
		evy.pb(event(q[i],P(p[i],-1),P(r[i],-1),0));
		evy.pb(event(s[i],P(p[i],-1),P(r[i],-1),2));
	}
	sort(all(evy));
	for(int i=0;i<evy.size();i++){
		event e = evy[i];
		//printf("%d %d %d %d\n",zy[e.x],zx[e.l.fi],zx[e.r.fi],e.type);
		if(e.type==0){
			seg.update(e.l.fi,e.r.fi+1,1);
		}else if(e.type==1){
			if(seg.query(e.l.fi,e.r.fi+1)==0){
				es.pb(edge(e.l.sec,e.r.sec,zx[e.r.fi]-zx[e.l.fi]));
			}
		}else{
			seg.update(e.l.fi,e.r.fi+1,-1);
		}
	}
	sort(all(es));
	ll base = 0ll;
	uf.init();
	for(int i=0;i<es.size();i++){
		edge e = es[i];
		//printf("%d %d %lld\n",e.from,e.to,e.cost);
		if(!uf.same(e.from,e.to)){
			uf.unite(e.from,e.to);
			uc.pb(e.cost);
			base += e.cost;
		}
	}
	int cnt = sz(uc);
	vector<ll> sum = uc;
	sum.pb(0ll);
	for(int i=cnt-1;i>=0;i--)sum[i]+=sum[i+1];
	for(int i=0;i<C;i++){
		if(N-cnt>H[i]){
			printf("-1\n");
		}else{
			ll ans = base+(N-cnt)*B[i];
			int k = upper_bound(all(uc),B[i])-uc.begin();
			int chg = min(H[i]-(N-cnt),cnt-k);
			ans += B[i]*(ll)chg-sum[cnt-chg];
			printf("%lld\n",ans);
		}
	}
	return 0;
}

マスコットの片付け

上下、左右を同時に扱ってDPの計算量を落とす。問題読んですぐに解法がわかった。

#define MOD 1000000007
int N,R,C;
int ax=INF,ay=INF,bx=-1,by=-1;
ll fac[4010];
ll dp[3010][3010];
ll mpow(ll a,ll x){
	ll res = 1ll;
	while(x){
		if(x&1)res = (res*a)%MOD;
		a = (a*a)%MOD;
		x >>= 1;
	}
	return res;
}
ll fact(int x){
	if(x<4000)return fac[x];
	ll res = 1;
	for(int i=1;i<=x;i++)res = (res*(ll)i)%MOD;
	return res;
}
ll func(int a,int b){
	ll res = fact(a+b);
	ll inva = mpow(fact(a),MOD-2);
	ll invb = mpow(fact(b),MOD-2);
	res = (res*inva%MOD)*invb%MOD;
	return res;
}
int main(){
	scanf("%d %d",&R,&C);
	scanf("%d",&N);
	for(int i=0;i<N;i++){
		int x,y;
		scanf("%d %d",&x,&y);
		ax = min(ax,x);
		ay = min(ay,y);
		bx = max(bx,x);
		by = max(by,y);
	}
	fac[0]=1ll;
	for(int i=1;i<4000;i++)fac[i]=(fac[i-1]*(ll)i)%MOD;
	int cx = bx-ax+1,cy = by-ay+1;
	int f = cx*cy-N;
	int rx = R-cx,ry = C-cy;
	dp[0][0]=1ll;
	for(int i=0;i<=rx;i++){
		for(int j=0;j<=ry;j++){
			if(i<rx)dp[i+1][j] = (dp[i+1][j]+dp[i][j]*fac[cy+j])%MOD;
			if(j<ry)dp[i][j+1] = (dp[i][j+1]+dp[i][j]*fac[cx+i])%MOD;
		}
	}
	ll ans = fact(f)*dp[rx][ry]%MOD;
	ans = ans*func(ax-1,R-bx)%MOD;
	ans = ans*func(ay-1,C-by)%MOD;
	printf("%lld\n",ans);
	return 0;
}

スパイ

オイラーツアー + 2次元imos法

vector<int> g[2][2010];
vector<int> euler[2];
int beg[2][2010],end[2][2010];
int root[2];
int k,idx;
void dfs(int v){
	beg[k][v]=idx++;
	for(int i=0;i<g[k][v].size();i++){
		dfs(g[k][v][i]);
	}
	end[k][v]=idx++;
}
int N,M;
int cnt[4010][4010];
void add(int a,int b,int c,int d){
	cnt[a][c]++;
	cnt[a][d]--;
	cnt[b][c]--;
	cnt[b][d]++;
}
int main(){
	scanf("%d %d",&N,&M);
	for(int i=0;i<N;i++){
		int p,q;
		scanf("%d %d",&p,&q);
		p--;q--;
		if(p>=0)g[0][p].pb(i);
		else root[0]=i;
		if(q>=0)g[1][q].pb(i);
		else root[1]=i;
	}
	for(k=0;k<2;k++){
		idx=0;
		dfs(root[k]);
	}
	/*for(int i=0;i<2;i++){
		for(int j=0;j<N;j++){
			printf("%d %d\n",beg[i][j],end[i][j]);
		}
	}*/
	for(int i=0;i<M;i++){
		int r,s;
		scanf("%d %d",&r,&s);
		r--;s--;
		add(beg[0][r],end[0][r],beg[1][s],end[1][s]);
	}
	for(int i=1;i<4010;i++){
		for(int j=0;j<4010;j++){
			cnt[i][j]+=cnt[i-1][j];
		}
	}
	for(int j=1;j<4010;j++){
		for(int i=0;i<4010;i++){
			cnt[i][j]+=cnt[i][j-1];
		}
	}
	for(int i=0;i<N;i++)printf("%d\n",cnt[beg[0][i]][beg[1][i]]);
	return 0;
}