Submission #530743

#	Time	Username	Problem	Language	Result	Execution time	Memory
530743		ammar2000	Street Lamps (APIO19_street_lamps)	C++17	20 / 100	247 ms	19260 KiB

street_lamps

#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=5e6+7;
ll INF=8e9+7;
int dx[] = {1 , -1 , 0 , 0};
int dy[] = {0 , 0 , 1 , -1};
int MOD=1e9+7;
ll n,q,a[SI],st[SI];
string s;
void build (int x,int l,int r)
{
    if(l==r)
    {
        st[x]=a[r];
        return;
    }
    ll m=(l+r)/2;
    build (2*x,l,m);
    build(2*x+1,m+1,r);
    st[x]=max(st[2*x],st[2*x+1]);
}
void update(int x,int l,int r ,int i,ll v)
{
   // cout <<l<<" "<<r<<"\n";
    if (l==r)
    {
        st[x]=v;
        return ;
    }
    ll m=(l+r)/2;
    if (i<=m)
        update(2*x,l,m,i,v);
    else update(2*x+1,m+1,r,i,v);
    st[x]=max(st[2*x],st[1+x*2]);
}
ll queries(int x,int l,int r,int ql,int qr)
{
    if (l>=ql&&r<=qr)
        return st[x];
    if (l>qr||r<ql)
        return -INF;
    ll m=(l+r)/2;
    return max(queries(2*x,l,m,ql,qr),queries(2*x+1,m+1,r,ql,qr));
}
int main()
{
   fast
   cin>>n>>q>>s;
   for (int i=0;i<n;i++)
   {
       if (s[i]=='0')
        a[i+1]=INF;
       else a[i+1]=0;
   }
   ll N=n+2;
   build (1,1,N);
   for (int h=1;h<=q;h++)
   {
       string is;
       cin>>is;
       if (is=="query")
        {
            ll le,ri;
            cin>>le>>ri;
            cout <<max(0ll,h-queries(1,1,N,le,ri-1))<<"\n";
        }
        else
        {
            ll x;
            cin>>x;
            update(1,1,N,x,h);
        }
   }
   // use scanf not cin
   return 0;
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 20
• Subtask 3: 20 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20