Codeforces Round #359 (Div. 1)

面白いかどうかはさておき、教育された感がある。普段Aからやってると抜かされるのでBからやったら大失敗した。

A B C D E Place
01:01 00:48 - 01:35 - 57th

A:
やるだけ。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
int dp[2][1<<7][2];
int p7[24];
int main(){
	int a,b;scanf("%d%d",&a,&b);
	int A=0;
	int B=0;
	int c=a-1;int d=b-1;
	while(c){
		c/=7;
		A++;
	}
	while(d){
		d/=7;
		B++;
	}
	p7[0]=1;
	for(int i=1;i<24;i++)p7[i]=p7[i-1]*7;
	a--;b--;
	if(!A)A++;
	if(!B)B++;
	dp[0][0][0]=1;
	for(int i=0;i<A+B;i++){
		int t=i%2;
		for(int j=0;j<(1<<7);j++)dp[!t][j][0]=dp[!t][j][1]=0;
		for(int j=0;j<(1<<7);j++){
			for(int k=0;k<2;k++){
				if(!dp[t][j][k])continue;
		//		printf("%d %d %d: %d\n",i,j,k,dp[i][j][k]);
				for(int l=0;l<7;l++){
					if(j&(1<<l))continue;
					int tk=k;
					if(i<A){
						if(k==0&&a/p7[A-i-1]%7<l)continue;
						else if(a/p7[A-i-1]%7>l)tk=1;
					}else{
						if(k==0&&b/p7[A+B-i-1]%7<l)continue;
						else if(b/p7[A+B-i-1]%7>l)tk=1;
					}
					if(i==A-1)tk=0;
					dp[!t][j+(1<<l)][tk]+=dp[t][j][k];
				}
			}
		}
	}
	int ret=0;
	for(int i=0;i<(1<<7);i++)for(int j=0;j<2;j++)ret+=dp[(A+B)%2][i][j];
	printf("%d\n",ret);
}

B:
慣れないdsu on treeを練習した。慣れない。あと定数倍がきつすぎ
ポインタに造詣がない人には、dsu on treeのあの書き方はデマ一より有用?

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
vector<int>g[310000];
int sz[310000];
int num;
int L[310000];
int R[310000];
int conv[310000];
int nx[310000];
void dfs(int a){
	sz[a]=1;
	L[a]=num;
	conv[num]=a;
	int mn=0;

	num++;
	for(int i=0;i<g[a].size();i++){
		dfs(g[a][i]);
		sz[a]+=sz[g[a][i]];
		if(mn<sz[g[a][i]]){
			mn=sz[g[a][i]];
			nx[a]=i;
		}
	}
	R[a]=num;
}
int ans[310000];
set<pair<pair<int,int>,int> > S;
set<pair<pair<int,int>,int> > T;
int mx[310000];
void solve(int a,int b){
	int to=-1;

	for(int i=0;i<g[a].size();i++){
		mx[a]=max(mx[a],sz[g[a][i]]);
		if(nx[a]==i){
			to=g[a][i];continue;
		}
		solve(g[a][i],0);

	}
	if(~to)solve(to,1);
	for(int i=0;i<g[a].size();i++){
		if(to==g[a][i])continue;
		solve(g[a][i],1);
	}
	if(!~ans[a]){

	T.insert(make_pair(make_pair(mx[a],sz[a]),a));
	S.insert(make_pair(make_pair(sz[a],mx[a]),a));
	int del=0;
	for(set<pair<pair<int,int>,int> > ::iterator it=S.begin();it!=S.end();it++){
		if((*it).first.first*2<sz[a])del++;
		else break;
	}
	for(int i=0;i<del;i++){
		pair<pair<int,int>,int> tmp=*(S.begin());
		S.erase(tmp);
		swap(tmp.first.first,tmp.first.second);
		T.erase(tmp);
	}
		ans[a]=(*(T.begin())).second;
	}
//	printf("%d: %d %d %d\n",a,T.begin()->first.first,T.begin()->first.second,T.begin()->second);
	if(b==0){
		for(int i=L[a];i<R[a];i++){
			T.erase(make_pair(make_pair(mx[conv[i]],sz[conv[i]]),conv[i]));
			S.erase(make_pair(make_pair(sz[conv[i]],mx[conv[i]]),conv[i]));
		}
	}
}
int main(){
	int a,b;scanf("%d%d",&a,&b);
	for(int i=0;i<a-1;i++){
		int p;scanf("%d",&p);p--;
		g[p].push_back(i+1);
	}
	for(int i=0;i<a;i++)ans[i]=-1;
	dfs(0);
	solve(0,1);
	while(b--){
		int p;scanf("%d",&p);p--;printf("%d\n",ans[p]+1);
	}
}

D:
計算量的には O(n log n+kn)で余裕そうに見えるがO(kn)パートが定数4のついたsetを使うやつで結構重そう、というか実際重い。
Time Limitの設定が総じて雑...?

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000010007;
const long long inf=mod*mod;
int r[110000];
int c[110000];
pair<int,int>p[110000];
pair<int,int>ev[210000];
long long ret[110000];
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	for(int i=0;i<a;i++){
		scanf("%d%d",r+i,c+i);
		ev[i*2+1]=make_pair(r[i],i+1);
		ev[i*2]=make_pair(r[i]+b,-i-1);
		p[i]=make_pair(c[i],r[i]);
	}
	std::sort(p,p+a);
	std::sort(ev,ev+a*2);
	int last=-mod;
	set<pair<int,pair<int,int> > > S;
	for(int i=0;i<a*2;i++){
	//	printf("%d: %d %d\n",i,ev[i].first,ev[i].second);
		if(i==0||ev[i].first!=ev[i-1].first){
			long long ks=ev[i].first-last;
			int las=-mod;
			int cnt=0;
			for(set<pair<int,pair<int,int> > >::iterator it=S.begin();it!=S.end();it++){
				if(it==S.begin()||((*it).first!=las)){

					if(cnt)ret[cnt]+=((long long)(*it).first-las)*ks;
					las=(*it).first;
				}
				cnt+=(*it).second.first;
			}
			last=ev[i].first;
		}
		if(ev[i].second>0){
			S.insert(make_pair(c[ev[i].second-1],make_pair(1,ev[i].second)));
			S.insert(make_pair(c[ev[i].second-1]+b,make_pair(-1,ev[i].second)));
		}else{
			S.erase(make_pair(c[-ev[i].second-1],make_pair(1,-ev[i].second)));
			S.erase(make_pair(c[-ev[i].second-1]+b,make_pair(-1,-ev[i].second)));
		}
	}
	for(int i=1;i<=a;i++){
		if(i!=1)printf(" ");
		printf("%I64d",ret[i]);
	}
	printf("\n");
}