Submission #516506

#	Time	Username	Problem	Language	Result	Execution time	Memory
516506		CSQ31	Street Lamps (APIO19_street_lamps)	C++17	0 / 100	5008 ms	23032 KiB

street_lamps

#include<bits/stdc++.h>
using namespace std;
const int sq = 550;
const int MAXN = 3e5+1;
int a[MAXN],ans[MAXN];
vector<array<int,3>>query[MAXN];
vector<int>upd[MAXN];
int dp[MAXN],n,q;

map<int,int>occ[sq];
int all[sq],delta[sq],L[sq],R[sq];
//is it all just the same number?delta plus on this block
void rebuild(int v){
	for(int i=L[v];i<=R[v];i++){
		if(all[v])dp[i] = delta[v];
		else dp[i]+=delta[v];
	}
	delta[v] = all[v] = 0;
}
void change(int l,int r,int c){
	int a = l/sq;
	int b = r/sq;
	
	for(int i = (l == L[a]? a:a+1); i <= (r == R[b]? b:b-1) ;i++){
		if(c)delta[i]++;
		else{
			all[i] = 1;
			delta[i] = 0;
			occ[i].clear();
			occ[i][0] = R[i] - L[i]+1;
		}
	}
	//just rebuild entire thing
	if(l != L[a]){
		rebuild(a);
		for(int i=l;i<=R[a];i++){
			if(c)dp[i]++;
			else dp[i] = 0;
		}
		for(int i=L[a];i<=R[a];i++)occ[a][dp[i]]++;
	}
	if(r != R[b]){
		rebuild(b);
		for(int i=L[b];i<=r;i++){
			if(c)dp[i]++;
			else dp[i] = 0;
		}
		for(int i=L[b];i<=R[b];i++)occ[b][dp[i]]++;
	}
	
}
int main()
{
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		upd[i] = {0};
		char c;
		cin>>c;
		a[i] = c-'0';
	}
	for(int i=0,j=0;i<=n;i+=sq){
		L[j] = i;
		R[j] = min(q,i+sq-1);
		all[j] = 1;
		occ[j][0] = R[j] - L[j]+1; 
		j++;
	}
	int cnt = 0;
	for(int i=1;i<=q;i++){
		string s;
		cin>>s;
		if(s=="toggle"){
			int x;cin>>x;
			upd[x].push_back(i);
		}else{
			int a,b;
			cin>>a>>b;
			query[b-1].push_back({a,i-1,cnt++});
		}
	}
	for(int i=1;i<=n;i++){
		int c = a[i];
		upd[i].push_back(q+1);
		for(int j=0;j+1<(int)(upd[i].size());j++){
			change(upd[i][j],upd[i][j+1]-1,c);
			c^=1;
		}
		for(auto x:query[i]){
			int t = x[1]/sq;
			for(int j=0;j<=(x[1] == R[t] ? t : t-1);j++){
				if(occ[j].find(i-x[0]+1 - delta[j]) != occ[j].end()){
					ans[x[2]]+=occ[j][i-x[0]+1 - delta[j]];
				}
			}
			if(x[1] != R[t]){
				rebuild(t);
				occ[t].clear();
				for(int j=L[t];j<=x[1];j++)ans[x[2]]+=dp[j] >= i-x[0]+1;
				for(int j=L[t];j<=R[t];j++)occ[t][dp[j]]++;
			}
		}
	}
	for(int i=0;i<cnt;i++)cout<<ans[i]<<'\n';
	
	
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20