oj.uz

Submission #404114

# Submission time Handle Problem Language Result Execution time Memory
404114 2021-05-13T19:34:48 Z Hazem Street Lamps (APIO19_street_lamps) C++14
20 / 100
 964 ms 11256 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define LL long long
#define F first
#define S second
#define pii pair<int,int>
#define piii pair<pair<int,int>,int>

const int N = 2e6+10;
const int M = 200;
const LL INF = 1e9;
const LL LINF = 2e18;
const LL MOD = 1e9+7;
const double PI = 3.141592653589793;

int ans[N],last[N];
int tree[N];

void update(int v,int tl,int tr,int pos,int val){

    if(tl==tr){
        tree[v] = val;
        return;
    }

    int mid = (tl+tr)/2;
    if(pos<=mid)
        update(v*2,tl,mid,pos,val);
    else 
        update(v*2+1,mid+1,tr,pos,val);

    tree[v] = max(tree[v*2],tree[v*2+1]);
}

int get(int v,int tl,int tr,int l,int r){

    if(tl>r||tr<l)
        return -INF;

    if(tl>=l&&tr<=r)
        return tree[v];

    int mid = (tl+tr)/2;
    return max(get(v*2,tl,mid,l,r),get(v*2+1,mid+1,tr,l,r));
}

int main(){

    //freopen("out.txt","w",stdout);

    int n,q;
    scanf("%d%d",&n,&q);
    string s;cin>>s;
    
    for(int i=0;i<n;i++)
        if(s[i]=='0')
            update(1,0,n,i,INF);


    for(int t = 1;t<=q;t++){
        string s1;cin>>s1;

        if(s1[0]=='q'){
            int l,r;scanf("%d%d",&l,&r);
            l--;r--;

            int val = get(1,0,n,l,r-1);
            printf("%d\n",val==INF?0:t-val);
        }
        else {
            int x;
            scanf("%d",&x);
            update(1,0,n,x-1,t);
        }
    }

}

Compilation message

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:53:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |     scanf("%d%d",&n,&q);
      |     ~~~~~^~~~~~~~~~~~~~
street_lamps.cpp:65:26: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |             int l,r;scanf("%d%d",&l,&r);
      |                     ~~~~~^~~~~~~~~~~~~~
street_lamps.cpp:73:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |             scanf("%d",&x);
      |             ~~~~~^~~~~~~~~

Subtask #1
0 / 20.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 413 ms 856 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 2 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 3 ms 328 KB Output is correct
4 Correct 3 ms 312 KB Output is correct
5 Correct 291 ms 9040 KB Output is correct
6 Correct 455 ms 9700 KB Output is correct
7 Correct 651 ms 10520 KB Output is correct
8 Correct 849 ms 8664 KB Output is correct
9 Correct 598 ms 3952 KB Output is correct
10 Correct 613 ms 4148 KB Output is correct
11 Correct 613 ms 4424 KB Output is correct
12 Correct 964 ms 11256 KB Output is correct
13 Correct 857 ms 8604 KB Output is correct

Subtask #4
0 / 20.0

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