Codeforces #745 Div1 : C. Train Maintenance

Cは1750ptだけど、こちらの方が解かれている。
https://codeforces.com/contest/1580/problem/C

問題

N個の電車がある。
i番の電車がT日目に導入された場合、その後X[i]日稼働してY[i]日メンテナンスして…を繰り返す。

M回のクエリが与えられるので、順次以下に答えよ。

• i日目には、1台の電車が、導入または撤去指定される。
• その後、i日目にメンテナンス中の電車の台数を求めよ。

解法

平方分割で解く。

• X[i]+Y[i]が√M以上の場合
  • 累積和の要領で、何日目に何台の電車がメンテナンス中か管理する。累積和の数列は、クエリ毎にO(M/(X[i]+Y[i]))箇所程度更新すればよい。
• X[i]+Y[i]が√M未満の場合
  • dp(n,m) := 現在日時をmで割った余りがnの時、メンテナンス中の電車数
  • とすると、クエリに応じdp(*,X[i]+Y[i])をインクリメントまたはデクリメントしていけばよい。

int N,M;
int X[202020],Y[202020];
int added[202020];

const int DI=100;
int mbt[DI+8][DI+8];
int dp[1<<20];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d%d",&N,&M);
	FOR(i,N) {
		scanf("%d%d",&X[i],&Y[i]);
		X[i]=min(X[i],1<<20);
		Y[i]=min(Y[i],1<<20);
	}
	FOR(i,M) {
		if(i) dp[i]+=dp[i-1];
		scanf("%d%d",&x,&y);
		y--;
		int S=X[y]+Y[y];
		int add;
		if(x==1) {
			added[y]=i;
			add=1;
		}
		else {
			add=-1;
		}
		
		if(S>=DI) {
			for(x=added[y];x<M;x+=S) {
				if(x+X[y]<M) dp[x+X[y]]+=add;
				if(x+S<M) dp[x+S]-=add;
				if(x+X[y]<i&&i<=x+S) dp[i]+=add;
			}
		}
		else {
			j=(added[y]+X[y])%(S);
			k=(added[y]+S)%(S);
			if(j<k) {
				for(x=j;x<k;x++) mbt[S][x]+=add;
			}
			else {
				for(x=0;x<k;x++) mbt[S][x]+=add;
				for(x=j;x<S;x++) mbt[S][x]+=add;
			}
		}
		
		
		int ret=dp[i];
		for(x=1;x<DI;x++) ret+=mbt[x][i%x];
		printf("%d\n",ret);
		
		
	}
}

まとめ

1500ptでもいい気がするな。