#pragma GCC optimize("O2")
#include <bits/stdc++.h>
#ifdef DEBUG
#include "debug.hpp"
#endif
using namespace std;
#define all(c) (c).begin(), (c).end()
#define traverse(c, it) for(auto it = (c).begin(); it != (c).end(); it++)
#define rep(i, N) for(int i = 0; i < (N); i++)
#define rep1(i, N) for(int i = 1; i <= (N); i++)
#define rep2(i, s, e) for(int i = (s); i <= (e); i++)
#define rep3(i, s, e, d) for(int i = (s); (d) >= 0 ? i <= (e) : i >= (e); i += (d))
#define pb push_back
#ifdef DEBUG
#define debug(x...) {dbg::depth++; string dbg_vals = dbg::to_string(x); dbg::depth--; dbg::fprint(__func__, __LINE__, #x, dbg_vals);}
#define light_debug(x) {dbg::light = 1; dbg::dout << __func__ << ":" << __LINE__ << " " << #x << " = " << x << endl; dbg::light = 0;}
#else
#define debug(x...)
#define light_debug(x)
#endif
template<typename T>
T& ckmin(T& a, T b){ return a = a > b ? b : a; }
template<typename T>
T& ckmax(T& a, T b){ return a = a < b ? b : a; }
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
template<int n>
struct BIT{
array<int, n + 1> a;
vi modifications;
void update(int i, int v){
for(i++; i <= n; i += i & -i) a[i] += v, modifications.pb(i);
}
int query(int i) const {
int s = 0;
for(i++; i; i -= i & -i) s += a[i];
return s;
}
void clear(){
for(int i : modifications) a[i] = 0;
modifications.clear();
}
};
struct interval{
int l, r, t; // [l, r) is one at time t;
bool operator <(const interval& x) const{
return l < x.l; // Enough, because no two intervals can have the same left endpoint (disjoint intervals).
}
};
string to_string(interval x){
return "{" + to_string(x.l) + ", " + to_string(x.r) + ", " + to_string(x.t) + "}";
}
struct offline_interval{
int l, r, t, d;
};
vi is_query, ans;
vector<offline_interval> a;
BIT<300001> bit;
void CDQ(int s, int e){
debug(s, e);
if(e - s <= 1)
return;
int m = (s + e) >> 1;
CDQ(s, m), CDQ(m, e);
vector<offline_interval> tmp;
tmp.reserve(e - s);
for(int x = s, y = m; x < m || y < e;){
if(x < m && (y == e || a[x].l <= a[y].l)){
if(is_query[a[x].t])
bit.update(a[x].r, a[x].d);
tmp.pb(a[x++]);
}else{
if(is_query[a[y].t])
ans[a[y].t] += bit.query(a[y].r);
tmp.pb(a[y++]);
}
}
bit.clear();
rep2(i, s, e - 1)
a[i] = tmp[i - s];
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
#ifdef DEBUG
freopen("debug", "w", stderr);
#endif
int n, q;
cin >> n >> q;
string status;
cin >> status;
is_query.resize(q + 1), ans.resize(q + 1);
set<interval> intervals;
for(int i = 0; i < n;){
while(i < n && status[i] == '0') i++;
int e = i;
for(; e < n && status[e] == '1'; e++);
if(e != i) intervals.insert({i, e, 0});
i = e;
}
auto toggle = [&](int i, int t){
auto next_ = intervals.upper_bound({i, -1, -1});
if(status[i] == '1'){
assert(next_ != intervals.begin());
auto cur = prev(next_);
auto tmp = *cur;
intervals.erase(cur);
a.pb({tmp.l, tmp.r, t, t - tmp.t});
int l = tmp.l, r = tmp.r;
if(l < i)
intervals.insert({l, i, t});
if(r > i + 1)
intervals.insert({i + 1, r, t});
status[i] = '0';
} else {
interval itvl = {i, i + 1, t};
if(next_ != intervals.begin() && prev(next_)->r == i){
auto pre = prev(next_);
itvl.l = pre->l;
a.pb({pre->l, pre->r, pre->t, t - pre->t});
intervals.erase(pre);
}
if(next_ != intervals.end() && next_->l == i + 1){
itvl.r = next_->r;
a.pb({next_->l, next_->r, next_->t, t - next_->t});
intervals.erase(next_);
}
intervals.insert(itvl);
status[i] = '1';
}
};
rep1(t, q){
string qtype;
cin >> qtype;
if(qtype == "toggle"){
int i;
cin >> i;
toggle(--i, t);
debug(t, status, intervals);
} else {
int l, r;
is_query[t] = 1;
cin >> l >> r;
--l, --r;
auto next_ = intervals.upper_bound({l, -1, -1});
if(next_ != intervals.begin()){
next_--;
if(next_->l <= l && r <= next_->r)
ans[t] += t - next_->t;
}
a.pb({l, r, t, 0});
}
debug(t);
}
CDQ(0, a.size());
rep1(i, q)
if(is_query[i]) cout << ans[i] << '\n';
#ifdef DEBUG
dbg::dout << "\nExecution time: " << clock() << "ms\n";
#endif
return 0;
}
| # |
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 |
Incorrect |
408 ms |
25996 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
512 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
512 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
512 KB |
Output isn't correct |
| 3 |
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 |
- |
