#include <bits/stdc++.h>
#ifdef local
#define debug(...) qqbx(#__VA_ARGS__, __VA_ARGS__)
#define safe cerr<<__PRETTY_FUNCTION__<<" line "<<__LINE__<<" safe\n"
template<typename H, typename ...T>
void qqbx(const char *s, const H h, T ...args) {
for(; *s && *s != ','; ++s) if(*s != ' ') std::cerr << *s;
std::cerr << " = " << h << (sizeof...(T) ? ", " : "\n");
if constexpr(sizeof...(T)) qqbx(++s, args...);
}
#else
#define debug(...) ((void)0)
#define safe ((void)0)
#endif // local
#define pb emplace_back
using namespace std;
typedef int64_t ll;
const int N = 300025;
const int inf = 1e9;
int n, q;
bool light[N];
map<pair<int,int>,int> last;
/* vector<tuple<int,int,int>> sg; */
struct Segtree {
struct node {
node *l, *r;
int sum;
node(int s) : sum(s), l(nullptr), r(nullptr) {}
void pull() {
sum = 0;
if(l) sum += l->sum;
if(r) sum += r->sum;
}
} *root = nullptr;
void add(int p, int d, int l, int r, node *&now) {
if(l+1 == r) return now = new node(d), void();
if(!now) now = new node(0);
int m = l+(r-l)/2;
if(p < m)
add(p, d, l, m, now->l);
else
add(p, d, m, r, now->r);
now->pull();
}
int query(int ql, int qr, int l, int r, node *now) {
if(!now || l >= qr || r <= ql) return 0;
if(ql <= l && r <= qr) return now->sum;
int m = l+(r-l)/2;
return query(ql, qr, l, m, now->l) + query(ql, qr, m, r, now->r);
}
} sgt[N];
void add(int L, int R, int d) {
/* sg.pb(L, R, d); */
for(int i = L+1; i < N; i += i&-i) sgt[i].add(R, d, 0, N, sgt[i].root);
}
void toggle(int x, int now) {
auto &mp = last;
light[x] = !light[x];
if(light[x]) {
int l = x, r = x;
if(x-1 >= 0 && light[x-1]) {
auto it = prev(mp.lower_bound({x, 0}));
auto [L, R] = it->first;
add(L, R, now - it->second);
l = L;
mp.erase(it);
}
if(x+1 < n && light[x+1]) {
auto it = mp.upper_bound({x, inf});
auto [L, R] = it->first;
add(L, R, now - it->second);
r = R;
mp.erase(it);
}
mp[{l, r}] = now;
} else {
auto it = prev(mp.upper_bound({x, inf}));
auto [L, R] = it->first;
add(L, R, now - it->second);
mp.erase(it);
if(L <= x-1) mp[{L, x-1}] = now;
if(R >= x+1) mp[{x+1, R}] = now;
}
}
int query(int a, int b, int now) {
--b;
int ans = 0;
{
if(light[a]) {
auto it = prev(last.upper_bound({a, inf}));
auto [l, r] = it->first;
if(l <= a && b <= r) ans += now - it->second;
}
}
for(int i = a+1; i > 0; i -= i&-i)
ans += sgt[i].query(b, N, 0, N, sgt[i].root);
/* for(auto [l, r, d]: sg) { */
/* if(l <= a && b <= r) */
/* ans += d; */
/* } */
return ans;
}
signed main() {
ios_base::sync_with_stdio(0), cin.tie(0);
string s;
cin >> n >> q >> s;
for(int i = 0; i < n; i++) if(s[i] == '1') toggle(i, 0);
for(int now = 1; now <= q; now++) {
char com[7];
cin >> com;
if(com[0] == 'q') {
int a, b;
cin >> a >> b;
--a, --b;
cout << query(a, b, now) << '\n';
} else if(com[0] == 't') {
int x;
cin >> x;
--x;
toggle(x, now);
}
}
}
Compilation message
street_lamps.cpp: In constructor 'Segtree::node::node(int)':
street_lamps.cpp:29:13: warning: 'Segtree::node::sum' will be initialized after [-Wreorder]
int sum;
^~~
street_lamps.cpp:28:15: warning: 'Segtree::node* Segtree::node::l' [-Wreorder]
node *l, *r;
^
street_lamps.cpp:30:9: warning: when initialized here [-Wreorder]
node(int s) : sum(s), l(nullptr), r(nullptr) {}
^~~~
street_lamps.cpp: In function 'void toggle(int, int)':
street_lamps.cpp:65:18: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
auto [L, R] = it->first;
^
street_lamps.cpp:72:18: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
auto [L, R] = it->first;
^
street_lamps.cpp:80:14: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
auto [L, R] = it->first;
^
street_lamps.cpp: In function 'int query(int, int, int)':
street_lamps.cpp:93:18: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
auto [l, r] = it->first;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
526 ms |
76244 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
1664 KB |
Output is correct |
| 2 |
Correct |
7 ms |
1664 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
1664 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
896 KB |
Output is correct |
| 2 |
Correct |
3 ms |
1152 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
1536 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
