#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef long long ll;
typedef pair<int,int> ii;
const int N = 3e5;
const int INF = 1e9;
int n, q;
int a[N+2];
map<int,int> bit[N+2];
void update(int r1, int r2, int c1, int c2, int v) {
for (int i = r1; i <= n+1; i += i&-i) {
for (int j = c1; j <= n+1; j += j&-j) {
bit[i][j] += v;
}
}
for (int i = r1; i <= n+1; i += i&-i) {
for (int j = c2+1; j <= n+1; j += j&-j) {
bit[i][j] -= v;
}
}
for (int i = r2+1; i <= n+1; i += i&-i) {
for (int j = c1; j <= n+1; j += j&-j) {
bit[i][j] -= v;
}
}
for (int i = r2+1; i <= n+1; i += i&-i) {
for (int j = c2+1; j <= n+1; j += j&-j) {
bit[i][j] += v;
}
}
}
int query(int r, int c) {
int ret = 0;
for (int i = r; i; i -= i&-i) {
for (int j = c; j; j -= j&-j) {
if (bit[i].count(j)) ret += bit[i][j];
}
}
return ret;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> q;
set<ii> st;
for (int i = 1; i <= n; i++) {
char x; cin >> x;
a[i] = x-'0';
if (a[i]) {
if (i == 1 || !a[i-1]) st.insert(ii(i,i));
else {
auto it = st.end(); it--;
int l = it->fi;
st.erase(it);
st.insert(ii(l,i));
}
}
}
for (int i = 1; i <= q; i++) {
string s; cin >> s;
if (s == "toggle") {
int x; cin >> x;
if (a[x]) {
auto it = st.upper_bound(ii(x,INF)); it--;
int l = it->fi, r = it->se;
st.erase(it);
if (l <= x-1) st.insert(ii(l,x-1));
if (x+1 <= r) st.insert(ii(x+1,r));
update(l,x,x+1,r,i);
}
else {
vector<set<ii>::iterator> del;
auto it = st.upper_bound(ii(x,INF));
int l, r;
if (it != st.end() && it->fi == x+1) {
r = it->se+1;
del.push_back(it);
}
if (it != st.begin()) {
it--;
if (it->se == x-1) {
l = it->fi;
del.push_back(it);
}
else l = x;
}
for (auto i : del) st.erase(i);
st.insert(ii(l,r-1));
update(l,x,x+1,r,-i);
}
a[x] ^= 1;
}
else {
int a, b; cin >> a >> b;
int ans = query(a,b);
auto it = st.upper_bound(ii(a,INF));
if (it != st.begin()) {
it--;
if (it->se+1 >= b) ans += i;
}
cout << ans << '\n';
}
}
return 0;
}
Compilation message
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:96:23: warning: 'l' may be used uninitialized in this function [-Wmaybe-uninitialized]
96 | update(l,x,x+1,r,-i);
| ~~~~~~^~~~~~~~~~~~~~
street_lamps.cpp:95:33: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
95 | st.insert(ii(l,r-1));
| ~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5029 ms |
14284 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5048 ms |
14412 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
15308 KB |
Output is correct |
| 2 |
Incorrect |
14 ms |
15088 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
14412 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5029 ms |
14284 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
