//#pragma GCC optimize("Ofast,unroll-loops,O3")
//#pragma GCC optimize("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma,tune=native")
#include<bits/stdc++.h>
//#include<bits/extc++.h>
//#pragma pack(1)
#define fast ios::sync_with_stdio(0); cin.tie(0);
#define int long long
#define pii pair<int,int>
#define x first
#define y second
#define N 300015
using namespace std;
//using namespace __gnu_pbds;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//typedef tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> order_multiset;
//typedef tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> order_set;
struct segtree{
int seg[4*N];
void change(int l,int r,int i,int p,int c){
if (l==r){
seg[i]=c;
return;
}
int mid=(l+r)>>1;
if (p<=mid) change(l,mid,2*i,p,c);
else change(mid+1,r,2*i+1,p,c);
seg[i]=max(seg[2*i],seg[2*i+1]);
}
int query(int l,int r,int i,int ll,int rr){
if (ll<=l&&rr>=r) return seg[i];
int mid=(l+r)>>1;
if (rr<=mid) return query(l,mid,2*i,ll,rr);
else if (ll>mid) return query(mid+1,r,2*i+1,ll,rr);
else return max(query(l,mid,2*i,ll,rr),query(mid+1,r,2*i+1,ll,rr));
}
}seg;
int n,q;
bool arr[N];
signed main(){
fast
cin>>n>>q;
for (int i=1;i<=n;i++){
char c; cin>>c;
arr[i]=c-'0';
if (arr[i])
seg.change(1,n,1,i,0);
else seg.change(1,n,1,i,1e9);
}
for (int t=1;t<=q;t++){
string str; cin>>str;
if (str=="toggle"){
int p; cin>>p;
arr[p]^=1;
seg.change(1,n,1,p,t);
}
else {
int l,r; cin>>l>>r;
int last=seg.query(1,n,1,l,r-1);
if (last>1e8) cout<<0<<'\n';
else cout<<t-last<<'\n';
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
71 ms |
784 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
288 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
141 ms |
9172 KB |
Output is correct |
6 |
Correct |
176 ms |
9528 KB |
Output is correct |
7 |
Correct |
212 ms |
9768 KB |
Output is correct |
8 |
Correct |
209 ms |
11348 KB |
Output is correct |
9 |
Correct |
74 ms |
1740 KB |
Output is correct |
10 |
Correct |
89 ms |
1772 KB |
Output is correct |
11 |
Correct |
81 ms |
1964 KB |
Output is correct |
12 |
Correct |
222 ms |
10060 KB |
Output is correct |
13 |
Correct |
213 ms |
11364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |