#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;
int n, q;
bool light[N];
map<pair<int,int>,int> last;
vector<tuple<int,int,int>> sg;
void add(int L, int R, int d) {
sg.pb(L, R, d);
}
void toggle(int x, int now) {
auto &mp = last;
light[x] = !light[x];
if(light[x]) {
int l = x, r = x;
if(x > 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 < n-1 && light[x+1]) {
auto it = mp.upper_bound({x, 0});
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, 0}));
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;
{
auto it = prev(last.upper_bound({a, 0}));
auto [l, r] = it->first;
if(l <= a && b <= r) ans += now - it->second;
}
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 function 'void toggle(int, int)':
street_lamps.cpp:35:18: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
auto [L, R] = it->first;
^
street_lamps.cpp:42:18: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
auto [L, R] = it->first;
^
street_lamps.cpp:50: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:62:14: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
auto [l, r] = it->first;
^
street_lamps.cpp:65:14: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
for(auto [l, r, d]: sg) {
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
640 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
640 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
640 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
