oj.uz

Submission #432717

# Submission time Handle Problem Language Result Execution time Memory
432717 2021-06-18T12:46:05 Z inwbear Street Lamps (APIO19_street_lamps) C++14
20 / 100
 411 ms 12588 KB 
#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

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

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 117 ms 728 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 1 ms 204 KB Output is correct
2 Correct 2 ms 308 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 264 ms 8888 KB Output is correct
6 Correct 321 ms 9604 KB Output is correct
7 Correct 360 ms 10308 KB Output is correct
8 Correct 411 ms 12588 KB Output is correct
9 Correct 124 ms 3904 KB Output is correct
10 Correct 138 ms 4244 KB Output is correct
11 Correct 139 ms 4420 KB Output is correct
12 Correct 396 ms 11172 KB Output is correct
13 Correct 400 ms 12556 KB Output is correct

Subtask #4
0 / 20.0

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

Subtask #5
0 / 20.0

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