Submission #910685

#	Time	Username	Problem	Language	Result	Execution time	Memory
910685		ibm2006	Street Lamps (APIO19_street_lamps)	C++17	0 / 100	132 ms	25228 KiB

street_lamps

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll n,i,j,k,l,r,x,y,z,w,s,t,a[1100000],b[1100000],q,ee,d[1100000],seg1[1100000],seg2[1100000];
char c[110000];
void f1(ll x)
{
    seg1[x]=(seg1[x*2]+seg1[x*2+1]);
    if(x==1)
        return;
    f1(x/2);
}
void f2(ll x)
{
    seg2[x]=max(seg2[x*2],seg2[x*2+1]);
    if(x==1)
        return;
    f2(x/2);
}
ll g1(ll x,ll y,ll z)
{
    if(y<l||x>r)
        return 0;
    if(l<=x&&y<=r)
        return seg1[z];
    return g1(x,(x+y)/2,z*2)+g1((x+y)/2+1,y,z*2+1);
}
ll g2(ll x,ll y,ll z)
{
    if(y<l||x>r)
        return 0;
    if(l<=x&&y<=r)
        return seg2[z];
    return max(g2(x,(x+y)/2,z*2),g2((x+y)/2+1,y,z*2+1));
}
int main()
{
    scanf("%lld %lld",&n,&q);
    for(i=1;i<=n;i++)
    {
        scanf("%01lld",&a[i]);
    }
    for(i=1;i<=n;i++)
    {
        b[i]=b[i-1]+a[i];
    }
    for(ee=1;ee<=q;ee++)
    {
        scanf("\n%s",c);
        if(c[0]=='t')
        {
            scanf("%lld",&x);
            seg2[x+262143]=ee;
            f2((x+262143)/2);
            seg1[x+262143]++;
            f1((x+262143)/2);
            continue;
        }
        scanf("%lld %lld",&x,&y);
        y--;
        l=x;
        r=y;
        z=g1(1,262144,1);
        if(b[y]-b[x-1]+z==y-x+1)
        {
            printf("%lld\n",ee-g2(1,262144,1));
            continue;
        }
        else
            printf("0\n");
    }
}

Compilation message (stderr)

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |     scanf("%lld %lld",&n,&q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
street_lamps.cpp:41:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         scanf("%01lld",&a[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~
street_lamps.cpp:49:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |         scanf("\n%s",c);
      |         ~~~~~^~~~~~~~~~
street_lamps.cpp:52:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |             scanf("%lld",&x);
      |             ~~~~~^~~~~~~~~~~
street_lamps.cpp:59:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |         scanf("%lld %lld",&x,&y);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~

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