oj.uz

Submission #910685

# Submission time Handle Problem Language Result Execution time Memory
910685 2024-01-18T07:11:04 Z ibm2006 Street Lamps (APIO19_street_lamps) C++17
0 / 100
 132 ms 25228 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 6492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 77 ms 8920 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10604 KB Output is correct
2 Correct 3 ms 10588 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 2 ms 4548 KB Output is correct
5 Incorrect 132 ms 25228 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10584 KB Output is correct
2 Incorrect 4 ms 10584 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 6492 KB Output isn't correct
2 Halted 0 ms 0 KB -