#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];
vector<pair<pair<int,int>,int>> vv;
/* struct JIZZZZZ { */
/* unordered_map<int,int> sum[N]; */
/* void add(int x, int y, int d) { */
/* ++x, ++y; */
/* for(int i = x; i < N; i += i&-i) for(int j = y; j < N; j += j&-j) sum[i][j] += d; */
/* } */
/* int query(int x, int y) { */
/* ++x, ++y; */
/* int res = 0; */
/* for(int i = x; i > 0; i -= i&-i) for(int j = y; j > 0; j -= j&-j) if(sum[i].count(j)) res += sum[i][j]; */
/* return res; */
/* } */
/* } DS; */
map<pair<int,int>,int> last;
void addRange(pair<int,int> rg, int d, int now) {
if(last.count(rg)) {
assert(d == -1);
int L = last[rg];
last.erase(rg);
vv.pb(rg, now - L);
/* auto [l, r] = rg; */
/* DS.add(l, N-1-r, now - L); */
} else {
assert(d == 1);
last[rg] = now;
}
}
map<int,int> lamps;
void toggle(int x, int now) {
map<int,int> &mp = lamps;
if(!light[x]) {
light[x] = true;
auto [it, succ] = mp.insert({x, x});
assert(succ);
if(next(it) != mp.end() && next(it)->first == x+1) {
it->second = next(it)->second;
addRange(*next(it), -1, now);
mp.erase(next(it));
}
if(it != mp.begin() && prev(it)->second == x-1) {
addRange(*prev(it), -1, now);
prev(it)->second = it->second;
mp.erase(it--);
}
addRange(*it, 1, now);
} else {
light[x] = false;
auto it = prev(mp.upper_bound(x));
addRange(*it, -1, now);
assert(it->first <= x && x <= it->second);
if(it->second >= x+1) {
auto [jt, succ] = mp.insert({x+1, it->second});
assert(succ);
addRange(*jt, 1, now);
}
if(it->first <= x-1) {
it->second = x-1;
addRange(*it, 1, now);
} else {
mp.erase(it);
}
}
debug(x);
for(auto [l, r]: mp) cerr << l << ' ' << r << '\n';
debug(mp.size());
}
int query(int a, int b, int now) {
/* int ans = DS.query(a, N-b); */
int ans = 0;
for(auto [rg, d]: vv) {
auto [l, r] = rg;
++r;
if(l <= a && b <= r) ans += d;
}
{
auto it = prev(lamps.upper_bound(a));
if(it->second+1 >= b) {
auto [l, r] = *it;
/* debug(l, r, a, b); */
assert(last.count(*it));
int L = last[*it];
ans += now - L;
}
}
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:56:14: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
auto [it, succ] = mp.insert({x, x});
^
street_lamps.cpp:75:18: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
auto [jt, succ] = mp.insert({x+1, it->second});
^
street_lamps.cpp:87:14: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
for(auto [l, r]: mp) cerr << l << ' ' << r << '\n';
^
street_lamps.cpp: In function 'int query(int, int, int)':
street_lamps.cpp:93:14: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
for(auto [rg, d]: vv) {
^
street_lamps.cpp:94:14: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
auto [l, r] = rg;
^
street_lamps.cpp:101:18: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
auto [l, r] = *it;
^
street_lamps.cpp:101:23: warning: unused variable 'l' [-Wunused-variable]
auto [l, r] = *it;
^
street_lamps.cpp:101:23: warning: unused variable 'r' [-Wunused-variable]
| # |
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 |
17 ms |
512 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 |
1248 ms |
1680 KB |
Output is correct |
| 2 |
Correct |
1280 ms |
1656 KB |
Output is correct |
| 3 |
Correct |
1024 ms |
1400 KB |
Output is correct |
| 4 |
Correct |
11 ms |
384 KB |
Output is correct |
| 5 |
Execution timed out |
5098 ms |
8588 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
504 ms |
1012 KB |
Output is correct |
| 2 |
Correct |
1066 ms |
1704 KB |
Output is correct |
| 3 |
Correct |
1695 ms |
2268 KB |
Output is correct |
| 4 |
Correct |
2348 ms |
2888 KB |
Output is correct |
| 5 |
Execution timed out |
5066 ms |
6720 KB |
Time limit exceeded |
| 6 |
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 |
- |
