#include <bits/stdc++.h>
#define all(dataStructure) dataStructure.begin(),dataStructure.end()
#define ll long long
using namespace std;
namespace std {
template <typename T, int D>
struct _vector : public vector <_vector <T, D - 1>> {
static_assert(D >= 1, "Dimension must be positive!");
template <typename... Args>
_vector(int n = 0, Args... args) : vector <_vector <T, D - 1>> (n, _vector <T, D - 1> (args...)) {}
};
// _vector <int, 3> a(n, m, k);: int a[n][m][k].
// _vector <int, 3> a(n, m, k, x);: int a[n][m][k] initialized with x.
template <typename T>
struct _vector <T, 1> : public vector <T> {
_vector(int n = 0, const T& val = T()) : vector <T> (n, val) {}
};
}
const int MAX = 3e5 + 3;
const ll MOD[] = {1000000007, 998244353};
int n, q, ans[MAX];
int state[MAX];
string st;
set <pair <int, int>> segmentOnActive;
struct FenwickTree {
int bit[MAX];
void update(int u, int v) {
for (; u > 0; u -= u & -u) bit[u] += v;
}
int get(int u) {
int res = 0;
for (; u <= n; u += u & -u) res += bit[u];
return res;
}
} fwSum, fwCnt;
struct up_t {
int time, l, r, val;
up_t(int a = 0, int b = 0, int c = 0, int d = 0) : time(a), l(b), r(c), val(d) {}
};
struct query_t {
int time, l1, l2, r;
query_t(int a = 0, int b = 0, int c = 0, int d = 0) : time(a), l1(b), l2(c), r(d) {}
};
void call(int leftBound, int rightBound, vector <up_t> &updates, vector <query_t> &queries) {
int updatesPointer = 0;
int mid = (leftBound + rightBound) / 2;
vector <query_t> leftQrs, rightQrs;
for (auto &[i, l1, l2, R] : queries) {
if (l1 == leftBound && l2 == rightBound) {
while (updatesPointer < (int)updates.size()) {
auto &[time, l, r, val] = updates[updatesPointer];
if (time > i) break;
fwSum.update(r, time * val);
fwCnt.update(r, val);
updatesPointer++;
}
ans[i] += fwCnt.get(R) * i - fwSum.get(R);
} else if (l2 <= mid) {
leftQrs.emplace_back(i, l1, l2, R);
} else if (l1 > mid) {
rightQrs.emplace_back(i, l1, l2, R);
} else {
leftQrs.emplace_back(i, l1, mid, R);
rightQrs.emplace_back(i, mid + 1, l2, R);
}
}
updatesPointer--;
while (updatesPointer >= 0) {
auto &[time, l, r, val] = updates[updatesPointer];
fwSum.update(r, -time * val);
fwCnt.update(r, -val);
updatesPointer--;
}
if (leftBound != rightBound) {
vector <up_t> leftUps, rightUps;
for (auto &[time, l, r, val] : updates) {
if (l <= mid) leftUps.emplace_back(time, l, r, val);
else rightUps.emplace_back(time, l, r, val);
}
call(leftBound, mid, leftUps, leftQrs);
call(mid + 1, rightBound, rightUps, rightQrs);
}
}
void Solve() {
cin >> n >> q;
cin >> st;
vector <up_t> updates;
vector <query_t> queries;
for (int i = 1; i <= n; i++) state[i] = st[i - 1] - '0';
for (int i = 1, j; i <= n; i++) {
if (state[i]) {
j = i;
while (j <= n && state[j]) j++;
j--;
segmentOnActive.insert(make_pair(i, j));
updates.emplace_back(0, i, j, 1);
i = j;
}
}
string qType;
int u, v;
for (int i = 1; i <= q; i++) {
ans[i] = -1;
cin >> qType >> u;
if (qType == "query") {
cin >> v;
ans[i] = 0;
queries.emplace_back(i, 1, u, v - 1);
} else {
state[u] ^= 1;
if (state[u] == 0) {
auto f = *prev(segmentOnActive.upper_bound(make_pair(u, -1)));
segmentOnActive.erase(f);
updates.emplace_back(i, f.first, f.second, -1);
if (state[u - 1]) {
segmentOnActive.insert(make_pair(f.first, u - 1));
updates.emplace_back(i, f.first, u - 1, 1);
}
if (state[u + 1]) {
segmentOnActive.insert(make_pair(u + 1, f.second));
updates.emplace_back(i, u + 1, f.second, 1);
}
} else {
int l = u, r = u;
if (state[u - 1]) {
auto f = *prev(segmentOnActive.upper_bound(make_pair(u, -1)));
segmentOnActive.erase(f);
updates.emplace_back(i, f.first, f.second, -1);
l = f.first;
}
if (state[u + 1]) {
auto f = *segmentOnActive.upper_bound(make_pair(u, -1));
segmentOnActive.erase(f);
updates.emplace_back(i, f.first, f.second, -1);
r = f.second;
}
segmentOnActive.insert(make_pair(l, r));
updates.emplace_back(i, l, r, 1);
}
}
}
call(1, n, updates, queries);
for (int i = 1; i <= q; i++) if (ans[i] != -1) cout << ans[i] << '\n';
}
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
#define TASK "TASK"
if (fopen(TASK".INP", "r")) {
freopen(TASK".INP", "r", stdin);
freopen(TASK".OUT", "w", stdout);
}
/* int TEST = 1; cin >> TEST; while (TEST--) */ Solve();
cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
return 0;
}
Compilation message
street_lamps.cpp: In function 'int32_t main()':
street_lamps.cpp:171:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
171 | freopen(TASK".INP", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:172:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
172 | freopen(TASK".OUT", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
132 ms |
33664 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
604 KB |
Output is correct |
| 2 |
Correct |
1 ms |
604 KB |
Output is correct |
| 3 |
Correct |
1 ms |
604 KB |
Output is correct |
| 4 |
Correct |
1 ms |
604 KB |
Output is correct |
| 5 |
Correct |
393 ms |
44744 KB |
Output is correct |
| 6 |
Correct |
474 ms |
52932 KB |
Output is correct |
| 7 |
Correct |
430 ms |
44232 KB |
Output is correct |
| 8 |
Correct |
240 ms |
34500 KB |
Output is correct |
| 9 |
Correct |
71 ms |
22972 KB |
Output is correct |
| 10 |
Correct |
63 ms |
25788 KB |
Output is correct |
| 11 |
Correct |
65 ms |
25732 KB |
Output is correct |
| 12 |
Correct |
220 ms |
34840 KB |
Output is correct |
| 13 |
Correct |
230 ms |
34000 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
600 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
