Submission #1005026

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005026		vjudge1	Street Lamps (APIO19_street_lamps)	C++17	40 / 100	1301 ms	5092 KiB

street_lamps

#include <bits/stdc++.h>

using namespace std;

int main()
{
	int n,q;
	cin>>n>>q;
	string s;
	cin>>s;
	if (n<=100)
	{
		int pre[n+1],ans[n][n+1]={};
		pre[0]=0;
		for (int i=0;i<n;i++)
			pre[i+1]=pre[i]+(s[i]-'0');
		for (int i=0;i<n;i++)
			for (int j=i+1;j<=n;j++)
				ans[i][j]=(pre[j]-pre[i]==j-i);
		while (q--)
		{
			string t;
			cin>>t;
			if (t=="query")
			{
				int a,b;
				cin>>a>>b;
				cout<<ans[a-1][b-1]<<endl;
			}
			else
			{
				int i;
				cin>>i;
				s[i-1]=char('0'+1-(s[i-1]-'0'));
			}
			pre[0]=0;
			for (int i=0;i<n;i++)
				pre[i+1]=pre[i]+(s[i]-'0');
			for (int i=0;i<n;i++)
				for (int j=i+1;j<=n;j++)
					ans[i][j]+=(pre[j]-pre[i]==j-i);
		}
	}
	else
	{
		int las[n],su[n]={};
		for (int i=0;i<n;i++)
			if (s[i]=='1')
				las[i]=0;
		for (int m=1;m<=q;m++)
		{
			string t;
			cin>>t;
			if (t=="toggle")
			{
				int i;
				cin>>i;
				i--;
				if (s[i]=='0')
				{
					las[i]=m;
					s[i]='1';
				}
				else
				{
					su[i]+=m-las[i];
					s[i]='0';
				}
			}
			else
			{
				int a,b;
				cin>>a>>b;
				a--;
				int ans=su[a];
				if (s[a]=='1')
					ans+=m-las[a];
				cout<<ans<<endl;
			}
		}
	}
	
	return 0;
}

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