oj.uz

Submission #1005042

# Submission time Handle Problem Language Result Execution time Memory
1005042 2024-06-22T06:30:16 Z vjudge1 Street Lamps (APIO19_street_lamps) C++17
40 / 100
 492 ms 18928 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
int const N=105;
int const N1=3e5+5;
int const mod=1e9+7;
int n,q;
string s;
int ans[N][N];
set<int> blocked;
int check(int a,int b){
	if( (blocked.lower_bound(a))==blocked.end() || (*(blocked.lower_bound(a)))>=b)
		return 1;
	return 0;
}
void solve1(){
	cin>>s;
	for(int i=0;i<n;i++)
		if(s[i]=='0')
			blocked.insert(i);
	while(q--){
		for(int i=0;i<=n;i++)
			for(int j=i;j<=n;j++)
				ans[i][j]+=check(i,j);
		string o;
		cin>>o;
		if(o=="toggle"){
			int t;
			cin>>t;
			t--;
			if(s[t]=='1'){
				blocked.insert(t);
				s[t]='0';
			}
			else{
				blocked.erase(t);
				s[t]='1';
			}
		}
		else{
			int a,b;
			cin>>a>>b;
			a--;b--;
			cout<<ans[a][b]<<endl;
		}
	}
}
vector<int> instance[N1];
void solve2(){
	cin>>s;
	for (int i = 0; i < n; ++i)
		if(s[i]=='1')
			instance[i].push_back(0);
	int c=0;
	while(q--){
		c++;
		string o;
		cin>>o;
		if(o=="toggle"){
			int t;
			cin>>t;
			t--;
			if(s[t]=='1'){
				instance[t].push_back(c);
				s[t]='0';
			}
			else{
				s[t]='1';
				instance[t].push_back(c);
			}
		}
		else{
			int a,b;
			cin>>a>>b;
			a--;b--;
			instance[a].push_back(c);
			int sm=0;
			for(int i=1;i<int(instance[a].size());i+=2)
				sm+=instance[a][i]-instance[a][i-1];
			instance[a].pop_back();
			cout<<sm<<endl;
		}
	}
}
int main(){
	cin>>n>>q;
	if(n<=100 && q<=100)
		solve1();
	else{
		// retur/n 0;
		solve2();
	}
	return 0;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 9300 KB Output is correct
2 Correct 257 ms 9316 KB Output is correct
3 Correct 250 ms 9296 KB Output is correct
4 Correct 321 ms 16148 KB Output is correct
5 Correct 329 ms 18052 KB Output is correct
6 Correct 281 ms 16112 KB Output is correct
7 Correct 489 ms 14304 KB Output is correct
8 Correct 492 ms 18928 KB Output is correct

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7256 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 2 ms 7260 KB Output is correct
4 Correct 6 ms 7516 KB Output is correct
5 Correct 6 ms 7516 KB Output is correct
6 Correct 6 ms 7516 KB Output is correct
7 Correct 3 ms 7516 KB Output is correct
8 Correct 279 ms 9300 KB Output is correct
9 Correct 257 ms 9316 KB Output is correct
10 Correct 250 ms 9296 KB Output is correct
11 Correct 321 ms 16148 KB Output is correct
12 Correct 329 ms 18052 KB Output is correct
13 Correct 281 ms 16112 KB Output is correct
14 Correct 489 ms 14304 KB Output is correct
15 Correct 492 ms 18928 KB Output is correct
16 Incorrect 2 ms 7516 KB Output isn't correct
17 Halted 0 ms 0 KB -