#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) {
addRange(*next(it), -1, now);
it->second = next(it)->second;
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);
#ifdef local
for(auto [l, r]: mp) cerr << l << ' ' << r << '\n';
#endif // local
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 addRange(std::pair<int, int>, int, int)':
street_lamps.cpp:44:14: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
auto [l, r] = rg;
^
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: In function 'int query(int, int, int)':
street_lamps.cpp:103:18: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
auto [l, r] = *it;
^
street_lamps.cpp:103:23: warning: unused variable 'l' [-Wunused-variable]
auto [l, r] = *it;
^
street_lamps.cpp:103:23: warning: unused variable 'r' [-Wunused-variable]
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
16768 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
32 ms |
33920 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 |
15 ms |
17408 KB |
Output is correct |
| 2 |
Correct |
17 ms |
17408 KB |
Output is correct |
| 3 |
Correct |
16 ms |
17408 KB |
Output is correct |
| 4 |
Correct |
15 ms |
17664 KB |
Output is correct |
| 5 |
Correct |
4924 ms |
212820 KB |
Output is correct |
| 6 |
Execution timed out |
5059 ms |
211656 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
17152 KB |
Output is correct |
| 2 |
Correct |
13 ms |
17280 KB |
Output is correct |
| 3 |
Correct |
15 ms |
17280 KB |
Output is correct |
| 4 |
Correct |
15 ms |
17408 KB |
Output is correct |
| 5 |
Correct |
2232 ms |
110844 KB |
Output is correct |
| 6 |
Correct |
3394 ms |
154576 KB |
Output is correct |
| 7 |
Correct |
4445 ms |
185940 KB |
Output is correct |
| 8 |
Execution timed out |
5064 ms |
213516 KB |
Time limit exceeded |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
16768 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
