#include <bits/stdc++.h>
template <class T>
using Vec = std::vector<T>;
struct Fenwick {
Vec<int> data;
Fenwick() = default;
Fenwick(const int n): data(n + 1) { }
void add(int i, const int x) {
for (i += 1; i < (int) data.size(); i += i & -i) {
data[i] += x;
}
}
int get(int i) const {
int ret = 0;
for (i += 1; i > 0; i -= i & -i) {
ret += data[i];
}
return ret;
}
};
struct Add2D {
Vec<Vec<int>> pts;
Vec<Fenwick> fen;
Add2D(const Vec<int> &x, const Vec<int> &y, const int n) {
pts.resize(n + 1);
fen.resize(n + 1);
for (int i = 0; i < (int) x.size(); ++i) {
for (int k = x[i] + 1; k <= n; k += k & -k) {
pts[k].push_back(y[i]);
}
}
for (int i = 1; i <= n; ++i) {
std::sort(pts[i].begin(), pts[i].end());
fen[i] = Fenwick(pts[i].size());
}
}
void add(int l, int r, const int d, const int u, const int v) {
for (l += 1; l < (int) pts.size(); l += l & -l) {
fen[l].add(std::lower_bound(pts[l].begin(), pts[l].end(), d) - pts[l].begin(), v);
fen[l].add(std::lower_bound(pts[l].begin(), pts[l].end(), u) - pts[l].begin(), -v);
}
for (r += 1; r < (int) pts.size(); r += r & -r) {
fen[r].add(std::lower_bound(pts[r].begin(), pts[r].end(), d) - pts[r].begin(), -v);
fen[r].add(std::lower_bound(pts[r].begin(), pts[r].end(), u) - pts[r].begin(), v);
}
}
int get(int x, const int y) const {
int ret = 0;
for (x += 1; x > 0; x -= x & -x) {
ret += fen[x].get(std::lower_bound(pts[x].begin(), pts[x].end(), y) - pts[x].begin());
}
return ret;
}
};
int main() {
int N, Q;
std::cin >> N >> Q;
Vec<int> state(N);
for (auto &x: state) {
char c;
std::cin >> c;
x = (c == '1');
}
std::set<int> off;
for (int i = 0; i < N; ++i) {
if (!state[i]) {
off.insert(i);
}
}
Vec<int> ans, X, Y;
Vec<std::tuple<int, int, int, int, int>> add;
Vec<std::pair<int, int>> qs;
qs.reserve(Q);
for (int t = 1; t <= Q; ++t) {
std::string type;
std::cin >> type;
if (type == "query") {
const auto idx = (int) ans.size();
int a, b;
std::cin >> a >> b;
a -= 1;
b -= 1;
const auto itr = off.lower_bound(a);
ans.push_back(itr == off.end() || *itr >= b ? t : 0);
X.push_back(a);
Y.push_back(b);
qs.emplace_back(idx, true);
}
else {
const auto idx = (int) add.size();
int s;
std::cin >> s;
s -= 1;
if (off.find(s) == off.end()) {
off.insert(s);
const auto itr = off.find(s);
const auto l = (itr == off.begin() ? 0 : *std::prev(itr) + 1);
const auto r = (std::next(itr) == off.end() ? N : *std::next(itr));
add.emplace_back(l, s, s + 1, r, t);
}
else {
const auto itr = off.find(s);
const auto l = (itr == off.begin() ? 0 : *std::prev(itr) + 1);
const auto r = (std::next(itr) == off.end() ? N : *std::next(itr));
add.emplace_back(l, s, s + 1, r, -t);
off.erase(itr);
}
qs.emplace_back(idx, false);
}
}
Add2D rect(X, Y, N + 1);
for (const auto [i, f]: qs) {
if (f) {
ans[i] += rect.get(X[i], Y[i]);
}
else {
const auto [l, r, d, u, v] = add[i];
rect.add(l, r + 1, d, u + 1, v);
}
}
for (const auto x: ans) {
std::cout << x << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
499 ms |
17016 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
