This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
using i32 = int;
using u32 = unsigned;
using i16 = short;
using u16 = unsigned short;
using ld = long double;
using ii = pair<int, int>;
const int inf = 1e9;
template<class T>
struct SegTree {
vector<T> st;
int n;
SegTree(int n) : n {n} {
st.assign(2 * n + 1, 0);
}
void upd(int k, T x) {
k += n;
st[k] = x;
for(k /= 2; k > 0; k /= 2) st[k] = max(st[2 * k], st[2 * k + 1]);
}
T query(int l, int r) {
T ans {};
for(l += n, r += n; l <= r; l /= 2, r /= 2) {
if(l & 1) ans = max(ans, st[l++]);
if(~r & 1) ans = max(ans, st[r--]);
}
return ans;
}
};
void solve() {
int n, q;
string s;
cin >> n >> q >> s;
SegTree<int> st(n);
for(int i = 0; i < n; ++i) {
if(s[i] == '1') st.upd(i, 0);
else st.upd(i, inf);
}
for(int i = 1; i <= q; ++i) {
string type;
int l, r;
cin >> type >> l;
--l;
if(type == "toggle") {
if(s[l] == '0') st.upd(l, i);
else st.upd(l, inf);
s[l] ^= 1;
} else {
cin >> r;
r -= 2;
cout << max(0, i - st.query(l, r)) << '\n';
}
}
}
int main() {
ios_base :: sync_with_stdio(false);
cin.tie(0);
int t = 1;
//cin >> t;
while(t--) solve();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |