AtCoder ABC #365 (トヨタ自動車プログラミングコンテスト2024#8) : G - AtCoder Office

Fの方が苦戦した。
https://atcoder.jp/contests/abc365/tasks/abc365_g

問題

N人の人が、部屋に出入りする記録がM回分ある。
クエリとして2人組が指定されるので、2人が同時に部屋にいた時間の総和を求めよ。

解法

出入り回数が多い人と少ない人で分けて考える。

• 多い人について、あらかじめbitsetや累積和で、部屋にいるタイミングやその長さを高速に計算できるようにしておく。
• 少ない人は、出入りしたタイミングのリストを持って置く

これを用いて、以下のように2人組のクエリを処理する。

• 出入り回数が少ない人同士の場合
  • 両者のリストをmerge sort風に処理して、互いに部屋にいる時間を算出する
• 出入り回数が少ない人と多い人の場合
  • 出入り回数が少ない人のリストを走査し、多い人の累積和を使いながら、互いに部屋にいる時間を算出する
• 出入り回数が多い人同士の場合
  • bitsetのandを取ることで、互いに部屋にいる時間を算出する

int N,M,Q;
vector<int> Vs[202020];
int T[202020],P[202020];
int id[202020];
bitset<202020> BS[101];
int Bsum[101][202020];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>T[i]>>P[i];
		P[i]--;
		Vs[P[i]].push_back(i);
	}
	
	x=0;
	FOR(i,N) {
		
		if(Vs[i].size()>=2000) {
			id[i]=x;
			int cur=0;
			FOR(j,M-1) {
				if(P[j]==i) cur^=1;
				Bsum[x][j+1]=Bsum[x][j];
				if(cur) {
					BS[x][j]=1;
					Bsum[x][j+1]+=T[j+1]-T[j];
				}
			}
			x++;
		}
		else {
			id[i]=-1;
		}
	}
	cin>>Q;
	map<pair<int,int>,int> R;
	FOR(i,Q) {
		cin>>x>>y;
		x--,y--;
		if(id[x]>=0) swap(x,y);
		
		if(R.count({x,y})) {
			cout<<R[{x,y}]<<endl;
			continue;
		}
		int ret=0;
		if(id[x]>=0) {
			auto B=BS[id[x]]&BS[id[y]];
			FOR(j,M-1) if(B[j]) ret+=T[j+1]-T[j];
		}
		else if(id[y]>=0) {
			FOR(j,Vs[x].size()/2) {
				ret+=Bsum[id[y]][Vs[x][j*2+1]]-Bsum[id[y]][Vs[x][j*2]];
			}
		}
		else {
			int xp=0,yp=0,pre=0;
			int xc=0,yc=0;
			while(xc<Vs[x].size()&&yc<Vs[y].size()) {
				if(xc==Vs[x].size()) {
					h1:
					if(xp&&yp) ret+=T[Vs[y][yc]]-pre;
					yp^=1;
					pre=T[Vs[y][yc]];
					
					yc++;
				}
				else if(yc==Vs[y].size()) {
					h2:
					if(xp&&yp) ret+=T[Vs[x][xc]]-pre;
					xp^=1;
					pre=T[Vs[x][xc]];
					xc++;
				}
				else if(Vs[x][xc]<Vs[y][yc]) {
					goto h2;
				}
				else {
					goto h1;
				}
			}
		}
		cout<<ret<<endl;
		R[{x,y}]=ret;
	}
	
}

まとめ

やっぱりFの方がAC数少なそう。