oj.uz

Submission #910695

# Submission time Handle Problem Language Result Execution time Memory
910695 2024-01-18T07:15:27 Z ibm2006 Street Lamps (APIO19_street_lamps) C++17
20 / 100
 351 ms 29856 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+524287]=ee;
            f2((x+524287)/2);
            seg1[x+524287]++;
            f1((x+524287)/2);
            continue;
        }
        scanf("%lld %lld",&x,&y);
        y--;
        l=x;
        r=y;
        z=g1(1,524288,1);
        if(b[y]-b[x-1]+z==y-x+1)
        {
            printf("%lld\n",ee-g2(1,524288,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 10588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14684 KB Output is correct
2 Correct 3 ms 14684 KB Output is correct
3 Correct 2 ms 8536 KB Output is correct
4 Correct 2 ms 4444 KB Output is correct
5 Correct 129 ms 25168 KB Output is correct
6 Correct 133 ms 29856 KB Output is correct
7 Correct 203 ms 27216 KB Output is correct
8 Correct 351 ms 16544 KB Output is correct
9 Correct 99 ms 8376 KB Output is correct
10 Correct 103 ms 8528 KB Output is correct
11 Correct 118 ms 8768 KB Output is correct
12 Correct 186 ms 15180 KB Output is correct
13 Correct 346 ms 16736 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14680 KB Output is correct
2 Incorrect 3 ms 14680 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 10588 KB Output isn't correct
2 Halted 0 ms 0 KB -