This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5+10;
int n, q;
string initial;
vector<int> toggles;
vector<int> events[maxn];
string query[maxn];
int aa[maxn], bb[maxn];
bool subtask_1(){
return n<=100 and q<=100;
}
bool subtask_2(){
bool ok = true;
for(int i=1; i<=q; i++){
if(query[i][0]=='q' and bb[i]-aa[i]!=1) ok = false;
}
return ok;
}
inline bool check(int x, int a, int b){
string now = initial;
for(int i=0; i<=x; i++){
now[toggles[i]] = 1;
}
bool ok = true;
for(int i=a; i<b; i++){
if(now[i] == '0') ok = false;
}
return ok;
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
cin >> n >> q;
initial.resize(n+2);
for(int i=1; i<=n; i++){
cin >> initial[i];
if(initial[i]=='1') events[i].push_back(0);
}
for(int i=1; i<=q; i++){
cin >> query[i];
if(query[i][0] == 'q') cin >> aa[i] >> bb[i];
else cin >> aa[i];
}
if(subtask_1()){
toggles.push_back(0);
for(int t=1; t<=q; t++){
string op = query[t];
if(op[0] == 'q'){
int a = aa[t], b = bb[t];
string now = initial;
int ans = 0;
for(int i=0; i<toggles.size(); i++){
if(now[toggles[i]]=='0') now[toggles[i]] = '1';
else now[toggles[i]] = '0';
bool ok = true;
for(int j=a; j<b; j++) if(now[j] == '0') ok = false;
if(ok) ans++;
}
cout << ans << '\n';
toggles.push_back(0);
}
else{
int i = aa[t];
toggles.push_back(i);
}
}
}
else if(subtask_2()){
for(int t=1; t<=q; t++){
string op = query[t];
if(op[0] == 'q'){
int a = aa[t], b = bb[t];
int ans = 0;
for(int i=0; i<events[a].size(); i++){
if(i%2){
ans += events[a][i] - events[a][i-1];
}
}
if(events[a].size()%2) ans += t - events[a].back();
cout << ans << '\n';
}
else{
int i = aa[t];
events[i].push_back(t);
}
}
}
else{
toggles.push_back(0);
for(int t=1; t<=q; t++){
string op = query[t];
if(op[0] == 'q'){
int a = aa[t], b = bb[t];
int ini = 0, fim = toggles.size()-1, meio, ans = t;
while(ini <= fim){
meio = (ini+fim) >> 1;
if(check(meio, a, b)){
fim = meio - 1;
ans = meio;
}
else{
ini = meio + 1;
}
}
cout << t-ans << '\n';
toggles.push_back(0);
}
else{
int i = aa[t];
toggles.push_back(i);
}
}
}
return 0;
}
Compilation message (stderr)
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:80:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<toggles.size(); i++){
~^~~~~~~~~~~~~~~
street_lamps.cpp:111:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<events[a].size(); i++){
~^~~~~~~~~~~~~~~~~
street_lamps.cpp:107:32: warning: unused variable 'b' [-Wunused-variable]
int a = aa[t], b = bb[t];
^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |