Submission #530107

#	Time	Username	Problem	Language	Result	Execution time	Memory
530107		ammar2000	Street Lamps (APIO19_street_lamps)	C++17	0 / 100	176 ms	16824 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=4e6+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[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;
      |                 ^

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