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>
#define ll long long
#define pb push_back
#define F first
#define S second
#define coy cout<<"YES\n"
#define con cout<<"NO\n"
#define co1 cout<<"-1\n"
#define sc(x) scanf("%lld",&x)
#define all(x) x.begin(),x.end()
#define fast ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
const int SI=3e5+7;
ll INF=8e18+7;
int dx[] = {1 , -1 , 0 , 0};
int dy[] = {0 , 0 , 1 , -1};
int MOD=1e9+7;
ll n,q,a[SI],st[4*SI];
string s;
void build (int x,int l,int r)
{
if (l==r)
{
st[x]=a[l];
return;
}
ll m=(l+r)/2;
build (2*x,l,m);
build (2*x+1,m+1,r);
st[x]=max(st[x*2],st[2*x+1]);
}
void update(int x,int l,int r,int in,int v)
{
if (l==r)
{
st[x]=v;
return ;
}
ll m=(l+r)/2;
if (in<=m)
update(2*x,l,m,in,v);
else update(2*x+1,m+1,r,in,v);
st[x]=max(st[x*2],st[2*x+1]);
}
ll get(int x,int l,int r,int ql,int qr)
{
if (r<ql||qr<l)
return -INF;
if (ql<=l&&qr>=r)
return st[x];
ll m=(l+r)/2;
ll ret=get(2*x,l,m,ql,qr);
ret=max(ret,get(2*x+1,m+1,r,ql,qr));
return ret;
}
int main()
{
fast
cin>>n>>q>>s;
for (int i=0;i<n;i++)
{
if (s[i]=='1')
a[i+1]=0;
else a[i+1]=INF;
}
ll N=1;
while (N<n)
N*=2;
build (1,1,N);
for (int h=1;h<=q;h++)
{
string info;
cin>>info;
if (info=="query")
{
ll le,ri;
cin>>le>>ri;
cout <<max(0ll,h-get(1,1,N,le,ri))<<"\n";
}
else
{
ll x,y;
cin>>x;
update(1,1,N,x,h);
}
}
// use scanf not cin
return 0;
}
Compilation message (stderr)
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:82:17: warning: unused variable 'y' [-Wunused-variable]
82 | ll x,y;
| ^
# | 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... |