oj.uz

Submission #1005026

# Submission time Handle Problem Language Result Execution time Memory
1005026 2024-06-22T06:19:23 Z vjudge1 Street Lamps (APIO19_street_lamps) C++17
40 / 100
 1301 ms 5092 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1301 ms 1164 KB Output is correct
2 Correct 234 ms 1104 KB Output is correct
3 Correct 260 ms 1360 KB Output is correct
4 Correct 256 ms 3720 KB Output is correct
5 Correct 305 ms 4128 KB Output is correct
6 Correct 246 ms 3716 KB Output is correct
7 Correct 490 ms 3540 KB Output is correct
8 Correct 453 ms 5092 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1301 ms 1164 KB Output is correct
9 Correct 234 ms 1104 KB Output is correct
10 Correct 260 ms 1360 KB Output is correct
11 Correct 256 ms 3720 KB Output is correct
12 Correct 305 ms 4128 KB Output is correct
13 Correct 246 ms 3716 KB Output is correct
14 Correct 490 ms 3540 KB Output is correct
15 Correct 453 ms 5092 KB Output is correct
16 Incorrect 1 ms 344 KB Output isn't correct
17 Halted 0 ms 0 KB -