oj.uz

Submission #865878

# Submission time Handle Problem Language Result Execution time Memory
865878 2023-10-25T01:57:23 Z jk410 Street Lamps (APIO19_street_lamps) C++17
20 / 100
 215 ms 11504 KB 
#include <iostream>
using namespace std;
const int INF=(int)1e9;
int N,Q;
string S;
int Tree[1<<20];
int update(int x,int v,int l,int r,int n){
    if (r<x||x<l)
        return Tree[n];
    if (l==r)
        return Tree[n]=v;
    int m=(l+r)>>1;
    return Tree[n]=max(update(x,v,l,m,n<<1),update(x,v,m+1,r,n<<1|1));
}
int query(int lx,int rx,int l,int r,int n){
    if (r<lx||rx<l)
        return 0;
    if (lx<=l&&r<=rx)
        return Tree[n];
    int m=(l+r)>>1;
    return max(query(lx,rx,l,m,n<<1),query(lx,rx,m+1,r,n<<1|1));
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>N>>Q>>S;
    for (int i=1; i<=N; i++){
        if (S[i-1]=='0')
            update(i,INF,1,N,1);
    }
    for (int t=1; t<=Q; t++){
        string s;
        cin>>s;
        if (s[0]=='t'){
            int x;
            cin>>x;
            update(x,t,1,N,1);
        }
        else{
            int l,r;
            cin>>l>>r;
            int mx=query(l,r-1,1,N,1);
            cout<<max(t-mx,0)<<"\n";
        }
    }
    return 0;
}

Subtask #1
0 / 20.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 68 ms 860 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 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 127 ms 9268 KB Output is correct
6 Correct 143 ms 9860 KB Output is correct
7 Correct 161 ms 10452 KB Output is correct
8 Correct 173 ms 8784 KB Output is correct
9 Correct 70 ms 3924 KB Output is correct
10 Correct 78 ms 4304 KB Output is correct
11 Correct 77 ms 4432 KB Output is correct
12 Correct 215 ms 11504 KB Output is correct
13 Correct 177 ms 8628 KB Output is correct

Subtask #4
0 / 20.0

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