代码TLE求调
查看原帖
代码TLE求调
760171
Binah_cyc楼主2024/8/4 17:04
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,sqm;
int x[200005],y[200005];
int cnt,cnt1[400005],cnt2[455][455];
int place[400005];
int ans;
char c;
inline void read(int &x)
{
	x=0;
	while(!isdigit(c)) c=getchar();
	while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();
}
inline void write(int x)
{
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
signed main()
{
	read(n),read(m);
	sqm=sqrt(m);
	for(int i=1; i<=n; i++) read(x[i]),read(y[i]);
	int op,k;
	for(int now=1; now<=m; now++)
	{
		read(op),read(k);
		int tp=x[k]+y[k];
		if(op==1)
		{
			if(tp>sqm) for(int i=now+x[k]; i<=m; i+=tp)
				{
					cnt1[i]++;
					if(i+y[k]<=m) cnt1[i+y[k]]--;
				}
			else
			{
				int l=(now+x[k])%(tp),r=(now-1)%(tp);
				if(l<=r) for(int i=l; i<=r; i++) cnt2[tp][i]++;
				else
				{
					for(int i=0; i<=r; i++) cnt2[tp][i]++;
					for(int i=l; i<=tp-1; i++) cnt2[tp][i]++;
				}
			}
			place[k]=now;
		}
		else
		{
			if(tp>sqm) for(int i=place[k]+x[k]; i<=m; i+=tp)
				{
					cnt1[i]--;
					if(i+y[k]<=m) cnt1[i+y[k]]++;
					if(i<now&&i+y[k]>=now) ans--;
				}
			else
			{
				int l=(place[k]+x[k])%(tp),r=(place[k]-1)%(tp);
				if(l<=r) for(int i=l; i<=r; i++) cnt2[tp][i]--;
				else
				{
					for(int i=0; i<=r; i++) cnt2[tp][i]--;
					for(int i=l; i<tp; i++) cnt2[tp][i]--;
				}
			}
		}
		ans+=cnt1[now];
		cnt=0;
		for(int i=1; i<=sqm; i++) cnt+=cnt2[i][now%i];
		write(ans+cnt),putchar('\n');
	}
	return 0;
}
2024/8/4 17:04
加载中...