Submission #432717

#	Time	Username	Problem	Language	Result	Execution time	Memory
432717		inwbear	Street Lamps (APIO19_street_lamps)	C++14	20 / 100	411 ms	12588 KiB

street_lamps

#include <bits/stdc++.h>
#define L (idx*2)
#define R ((idx*2)+1)
using namespace std;
int n,m,seq[1200005],a,b;
char c[300005],qq[10];
void up(int st,int ed,int idx,int pos,int val)
{
    int mid=(st+ed)/2;
    if(pos<st||pos>ed)return;
    if(st==ed)
    {
        seq[idx]=val;
        return;
    }
    up(st,mid,L,pos,val);
    up(mid+1,ed,R,pos,val);
    seq[idx]=max(seq[L],seq[R]);
    return;
}
int mx(int st,int ed,int idx,int ll,int rr)
{
    int mid=(st+ed)/2;
    if(rr<st||ll>ed)return 0;
    if(ll<=st&&rr>=ed)return seq[idx];
    return max(mx(st,mid,L,ll,rr),mx(mid+1,ed,R,ll,rr));
}
int main()
{
    scanf("%d %d",&n,&m);
    scanf("%s",c+1);
    for(int i=1;i<=n;i++)
    {
        if(c[i]=='1')up(1,n,1,i,1);
        else up(1,n,1,i,m+1);
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%s",qq+1);
        if(qq[1]=='t')
        {
            scanf("%d",&a);
            up(1,n,1,a,i+1);
        }
        else
        {
            scanf("%d %d",&a,&b);
            printf("%d\n",max(0,i+1-mx(1,n,1,a,b-1)));
        }
    }
}

Compilation message (stderr)

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:30:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     scanf("%d %d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~
street_lamps.cpp:31:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |     scanf("%s",c+1);
      |     ~~~~~^~~~~~~~~~
street_lamps.cpp:39:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |         scanf("%s",qq+1);
      |         ~~~~~^~~~~~~~~~~
street_lamps.cpp:42:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |             scanf("%d",&a);
      |             ~~~~~^~~~~~~~~
street_lamps.cpp:47:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |             scanf("%d %d",&a,&b);
      |             ~~~~~^~~~~~~~~~~~~~~

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