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;
#define endl '\n'
//#define int long long
vector<int> t;
int traverse(int v, int tl, int tr, int l, int r){
//cout << tl << " " << tr << " " << l << " " << r << endl;
if (tl == l && tr == r){
return t[v];
}
int tm = (tl + tr) / 2;
if (r <= tm){
return traverse(v * 2, tl, tm, l, r);
}
if (l >= tm + 1){
return traverse(v * 2 + 1, tm + 1, tr, l, r);
}
return max(traverse(v * 2, tl, tm, l, tm), traverse(v * 2 + 1, tm + 1, tr, tm + 1, r));
}
void update(int v, int tl, int tr, int val, int pos){
if (tl == tr){
t[v] = val;
return;
}
int tm = (tl + tr) / 2;
if (pos <= tm){
update(v * 2, tl, tm, val, pos);
}
if (pos > tm){
update(v * 2 + 1, tm + 1, tr, val, pos);
}
t[v] = max(t[v * 2], t[v * 2 + 1]);
}
signed main(){
cin.tie(0);
iostream::sync_with_stdio(0);
int n, q;
cin >> n >> q;
t.resize(n * 4);
string lamps;
cin >> lamps;
for (int i = 0; i < n; ++i){
if (lamps[i] == '1'){
update(1, 0, n - 1, 0, i);
}
else{
update(1, 0, n - 1, 400000, i);
}
}
vector<int> l(n);
for (int i = 0; i < n; ++i){
if (lamps[i] == '0'){
l[i] = 400000;
}
}
for (int i = 0; i < q; ++i){
string s; int a, b;
cin >> s;
if (s == "toggle"){
cin >> a;
update(1, 0, n - 1, i + 1, a - 1);
}
else{
cin >> a >> b;
int out = traverse(1, 0, n - 1, a - 1, b - 2);
//cout << "debug: " << out << endl;
if (out == 400000){
cout << 0 << endl;
}
else{
cout << i - out + 1 << endl;
}
}
}
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... |