This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//Be Name Khoda
// 06:10 - 13:15
#include<bits/stdc++.h>
#pragma GCC optimize ("unroll-loops")
using namespace std;
typedef long long ll;
typedef long double ld;
#define all(x) x.begin(), x.end()
#define pll pair<ll, ll>
#define pii pair<int, int>
#define plll pair<pll, ll>
#define piii pair<pii, int>
#define piiii pair<pii, pii>
const int mxn = 3e5 + 16;
int n, q, v, u;
string s, h, cur;
vector<piii> qu;
vector<int> change[mxn];
int last[mxn];
bool mark[mxn];
void input() {
cin >> n >> q;
cin >> s;
cur = s;
for(int i = 0; i < q; i++) {
cin >> h;
if(h == "query") {
cin >> v >> u;
v--, u--;
qu.push_back({{1, v}, u});
}
else {
cin >> v;
v--;
qu.push_back({{2, v}, v});
}
}
}
void solve() {
if(q <= 100 && n <= 100) {
for(int i = 0; i < qu.size(); i++) {
if(qu[i].first.first == 1) {
int cnt = 0;
cur = s;
v = qu[i].first.second, u = qu[i].second;
for(int j = 0; j <= i; j++) {
bool b = true;
for(int w = v; w < u; w++) {
if(cur[w] == '0') {
b = false;
break;
}
}
if(b) {
cnt++;
}
if(qu[j].first.first == 2) {
if(cur[qu[j].second] == '1') cur[qu[j].second] = '0';
else {
cur[qu[j].second] = '1';
}
}
}
cout << cnt << endl;
}
}
return;
}
for(int i = 0; i < n; i++) {
change[i].push_back(0);
if(s[i] == '1') {
mark[i] = 1;
last[i] = 1;
}
else {
mark[i] = 0;
}
}
for(int i = 0; i < qu.size(); i++) {
if(qu[i].first.first == 1) {
v = qu[i].first.second;
if(mark[v]) {
last[v] += (i - change[v].back());
}
change[v].push_back(i);
cout << last[v] << endl;
}
else {
v = qu[i].first.second;
if(!mark[v]) {
mark[v] = 1;
change[v].push_back(i);
}
else {
mark[v] = 0;
last[v] += (i - change[v].back());
change[v].push_back(i);
}
}
}
}
int main() {
ios_base::sync_with_stdio(false);
input(), solve();
return 0;
}
/*
5 7
11011
query 1 2
query 1 2
query 1 6
query 3 4
toggle 3
query 3 4
query 1 6
*/
Compilation message (stderr)
street_lamps.cpp: In function 'void solve()':
street_lamps.cpp:50:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | for(int i = 0; i < qu.size(); i++) {
| ~~^~~~~~~~~~~
street_lamps.cpp:88:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
88 | for(int i = 0; i < qu.size(); i++) {
| ~~^~~~~~~~~~~
# | 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... |