#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 = 3e5 + 10;
int n, q;
int tr[N][19];
vector<int> bit[N];
bool a[N];
set<pair<int, int>> st;
struct query {
string s;
int i, a, b;
};
query d[N];
void fakeup(int f, int l) {
while(f <= n + 1) {
bit[f].push_back(l);
f += f & -f;
}
}
void fakeget(int f, int l) {
while(f) {
bit[f].push_back(l);
f -= f & -f;
}
}
void up(int f, int l, int val) {
while(f <= n + 1) {
int y = lower_bound(bit[f].begin(), bit[f].end(), l) - bit[f].begin() + 1;
while(y) {
tr[f][y - 1] += val;
y -= y & -y;
}
f += f & -f;
}
}
int get(int f, int l) {
int res = 0;
while(f) {
int y = lower_bound(bit[f].begin(), bit[f].end(), l) - bit[f].begin() + 1;
while(y <= n + 1) {
res += tr[f][y - 1];
y += y & -y;
}
f -= f & -f;
}
return res;
}
void fakeadd(int f, int l) {
fakeup(f, l + 1);
st.insert({f, l});
}
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');
st.insert({-1, -1});
st.insert({1e9, 1e9});
int f = -1;
forin(i,1,n + 1) {
if(f == -1 && a[i]) f = i;
if(f != -1 && !a[i]) {
fakeadd(f, i - 1);
f = -1;
}
}
forin(j,1,q) {
cin>>d[j].s;
string s = d[j].s;
if(s[0] == 't') {
int i; cin>>i;
d[j].i = i;
auto i1 = st.upper_bound({i, 1e9});
auto i2 = i1--;
pair<int, int> cur = *i1;
pair<int, int> aft = *i2;
if(cur.la + 1 < i && i < aft.fi - 1) fakeadd(i, i);
else if(i == cur.la + 1 && i == aft.fi - 1) {
st.erase(i1); fakeup(cur.fi, cur.la + 1);
st.erase(i2); fakeup(aft.fi, aft.la + 1);
fakeadd(cur.fi, aft.la);
}
else if(i == cur.la + 1) {
st.erase(i1); fakeup(cur.fi, cur.la + 1);
fakeadd(cur.fi, cur.la + 1);
}
else if(i == aft.fi - 1) {
st.erase(i2); fakeup(aft.fi, aft.la + 1);
fakeadd(aft.fi - 1, aft.la);
}
else if(i <= cur.la) {
st.erase(i1); fakeup(cur.fi, cur.la + 1);
if(cur.fi != aft.la) {
if(i == cur.fi) fakeadd(cur.fi + 1, cur.la);
else if(i == cur.la) fakeadd(cur.fi, cur.la - 1);
else {
fakeadd(cur.fi, i - 1);
fakeadd(i + 1, cur.la);
}
}
}
}
else {
cin>>d[j].a>>d[j].b;
fakeget(d[j].a, d[j].b);
}
}
forin(i,1,n + 1) {
sort(bit[i].begin(), bit[i].end());
bit[i].resize(unique(bit[i].begin(), bit[i].end()) - bit[i].begin());
}
while(!st.empty()) st.erase(st.begin());
st.insert({-1, -1});
st.insert({1e9, 1e9});
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 = d[j].s;
if(s[0] == 't') {
int i = d[j].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(cur.fi != cur.la) {
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 = d[j].a, b = d[j].b;
pair<int, int> it = *--st.upper_bound({a, 1e9});
if(it.fi <= a && 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:62:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
62 | freopen("Task.inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:63:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
63 | freopen("WA.out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
11 ms |
21460 KB |
Output is correct |
| 2 |
Correct |
12 ms |
21440 KB |
Output is correct |
| 3 |
Correct |
11 ms |
21476 KB |
Output is correct |
| 4 |
Incorrect |
11 ms |
21436 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
275 ms |
31856 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
13 ms |
21612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
11 ms |
21612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
11 ms |
21460 KB |
Output is correct |
| 2 |
Correct |
12 ms |
21440 KB |
Output is correct |
| 3 |
Correct |
11 ms |
21476 KB |
Output is correct |
| 4 |
Incorrect |
11 ms |
21436 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
