#include<bits/stdc++.h>
#define forin(i,a,b) for(int i=a;i<=b;++i)
#define fi first
#define la second
using namespace std;
const int N = 1e3 + 10;
int n, q;
int tr[N][N], flag[N][N];
bool a[N];
set<pair<int, int>> st;
void up(int f, int l, int val) {
while(f <= n + 1) {
int x = l;
while(x) {
tr[f][x] += val;
x -= x & -x;
}
f += f & -f;
}
}
int get(int f, int l) {
int res = 0;
while(f) {
int x = l;
while(x <= n + 1) {
res += tr[f][x];
x += x & -x;
}
f -= f & -f;
}
return res;
}
void add(int f, int l, int val) {
up(f, l + 1, val);
st.insert({f, l});
}
int main () {
cin.tie(0)->sync_with_stdio(0);
if(fopen("Task.inp","r")) {
freopen("Task.inp","r",stdin);
freopen("WA.out","w",stdout);
}
cin>>n>>q;
string s; cin>>s;
s = " " + s;
forin(i,1,n) a[i] = (s[i] == '1');
int f = -1;
forin(i,1,n + 1) {
if(f == -1 && a[i]) f = i;
if(f != -1 && !a[i]) {
add(f, i - 1, q);
f = -1;
}
}
forin(j,1,q) {
string s; cin>>s;
if(s[0] == 't') {
int i; cin>>i;
a[i] = 1 - a[i];
auto i1 = st.upper_bound({i, 1e9});
auto i2 = i1--;
pair<int, int> cur = *i1;
pair<int, int> aft = *i2;
int val = q - j;
if(cur.la + 1 < i && i < aft.fi - 1) add(i, i, val);
else if(i == cur.la + 1 && i == aft.fi - 1) {
st.erase(i1); up(cur.fi, cur.la + 1, -val);
st.erase(i2); up(aft.fi, aft.la + 1, -val);
add(cur.fi, aft.la, val);
}
else if(i == cur.la + 1) {
st.erase(i1); up(cur.fi, cur.la + 1, -val);
add(cur.fi, cur.la + 1, val);
}
else if(i == aft.fi - 1) {
st.erase(i2); up(aft.fi, aft.la + 1, -val);
add(aft.fi - 1, aft.la, val);
}
else if(i <= cur.la) {
st.erase(i1); up(cur.fi, cur.la + 1, -val);
if(i == cur.fi) add(cur.fi + 1, cur.la, val);
else if(i == cur.la) add(cur.fi, cur.la - 1, val);
else {
add(cur.fi, i - 1, val);
add(i + 1, cur.la, val);
}
}
}
else {
int a, b; cin>>a>>b;
pair<int, int> it = *--st.upper_bound({a, 1e9});
if(b <= it.la + 1) cout<<get(a, b) - (q - j)<<"\n";
else cout<<get(a, b)<<"\n";
}
}
}
Compilation message
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:40:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
40 | freopen("Task.inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:41:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
41 | freopen("WA.out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
1108 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2388 KB |
Output is correct |
| 2 |
Runtime error |
5 ms |
4692 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
