#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define all(v) v.begin(),v.end()
#define P pair<int,int>
#define len(s) (int)s.size()
template<class T> inline bool chmin(T &a, T b){
if(a>b){a=b;return true;}
return false;
}
template<class T> inline bool chmax(T &a, T b){
if(a<b){a=b;return true;}
return false;
}
constexpr int mod = 1e9+7;
constexpr long long inf = 3e18;
template<typename Monoid,typename OperatorMonoid,typename F,typename G,typename H>
struct Segtree{
int size=1;
vector<Monoid>dat;
vector<OperatorMonoid>lazy;
const F f;
const G g;
const H h;
Monoid M;
OperatorMonoid OM;
void set(int a,Monoid x){
dat[a+size-1]=x;
}
void init(){
for(int i=size-2;i>=0;i--){
dat[i]=f(dat[i*2+1],dat[i*2+2]);
}
}
void eval(int k,int l,int r){
if(lazy[k]!=OM){
dat[k]=g(dat[k],lazy[k],(r-l));
if(r-l>1){
lazy[2*k+1]=h(lazy[2*k+1],lazy[k]);
lazy[2*k+2]=h(lazy[2*k+2],lazy[k]);
}
lazy[k]=OM;
}
}
void update(int a,int b,OperatorMonoid M,int k=0,int l=0,int r=-1){
if(r==-1)r=size;
eval(k,l,r);
if(r<=a||b<=l)return;
if(a<=l&&r<=b){
lazy[k]=h(lazy[k],M);
eval(k,l,r);
return;
}
update(a,b,M,k*2+1,l,(l+r)/2);
update(a,b,M,k*2+2,(l+r)/2,r);
dat[k]=f(dat[k*2+1],dat[k*2+2]);
}
Monoid query(int a,int b,int k=0,int l=0,int r=-1){
if(r==-1)r=size;
eval(k,l,r);
if(r<=a||b<=l)return M;
if(a<=l&&r<=b)return dat[k];
Monoid lv=query(a,b,k*2+1,l,(l+r)/2);
Monoid rv=query(a,b,k*2+2,(l+r)/2,r);
return f(lv,rv);
}
Segtree(int x,F f,G g,H h,Monoid M,OperatorMonoid OM)
:f(f),g(g),h(h),M(M),OM(OM){
while(size<x)size*=2;
dat.resize(size*2-1,M);
lazy.resize(size*2-1,OM);
}
};
auto f=[](int a,int b){return a+b;};
auto g=[](int a,int b,int sz){return b;};
auto h=[](int a,int b){return b;};
int N,Q;
string S;
string query[300005];
int A[300005],B[300005];
signed main(){
cin>>N>>Q>>S;
Segtree<int,int,decltype(f),decltype(g),decltype(h)>segtree(N,f,g,h,0,-1);
rep(i,N)segtree.set(i,(S[i]=='1'?0:1));
segtree.init();
rep(i,Q){
cin>>query[i];
if(query[i]=="query"){
cin>>A[i]>>B[i];A[i]--;B[i]--;
cout<<(segtree.query(A[i],B[i])==0)*(i+1)<<endl;
}else break;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
9728 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
9728 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
9728 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
9856 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
9728 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
