oj.uz

Submission #974716

# Submission time Handle Problem Language Result Execution time Memory
974716 2024-05-03T16:56:21 Z Abito Street Lamps (APIO19_street_lamps) C++17
20 / 100
 203 ms 12624 KB 
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define ppb pop_back
#define ep insert
#define endl '\n'
#define elif else if
#define pow pwr
#define sqrt sqrtt
//#define int long long
#define ll long long
typedef unsigned long long ull;
using namespace std;
const int N=3e5+5;
int n,q,seg[4*N+5];
bool a[N];
int build(int x,int l,int r){
    if (l==r){
        if (a[l]) seg[x]=0;
        else seg[x]=q+100;
        return seg[x];
    }
    int mid=(l+r)/2;
    return seg[x]=max(build(x*2,l,mid),build(x*2+1,mid+1,r));
}
void edit(int x,int l,int r,int idx,int val){
    if (l==r){
        seg[x]=val;
        return;
    }int mid=(l+r)/2;
    if (idx<=mid) edit(x*2,l,mid,idx,val);
    else edit(x*2+1,mid+1,r,idx,val);
    seg[x]=max(seg[x*2],seg[x*2+1]);
    return;
}
int query(int x,int l,int r,int lx,int rx){
    if (l>=lx && r<=rx) return seg[x];
    if (l>rx || r<lx) return INT_MIN;
    int mid=(l+r)/2;
    return max(query(x*2,l,mid,lx,rx),query(x*2+1,mid+1,r,lx,rx));
}
int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    cin>>n>>q;
    for (int i=1;i<=n;i++){
        char c;cin>>c;
        if (c=='1') a[i]=1;
    }
    build(1,1,n);
    for (int i=1;i<=q;i++){
        string s;cin>>s;
        if (s=="toggle"){
            int x;cin>>x;
            edit(1,1,n,x,i);
        }
        else{
            int l,r;cin>>l>>r;
            cout<<max(0,i-query(1,1,n,l,r-1))<<endl;
        }
    }
    return 0;
}

Subtask #1
0 / 20.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 76 ms 6056 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 2648 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 90 ms 8916 KB Output is correct
6 Correct 136 ms 9712 KB Output is correct
7 Correct 150 ms 10320 KB Output is correct
8 Correct 185 ms 12616 KB Output is correct
9 Correct 73 ms 5964 KB Output is correct
10 Correct 80 ms 6224 KB Output is correct
11 Correct 83 ms 6484 KB Output is correct
12 Correct 203 ms 11004 KB Output is correct
13 Correct 185 ms 12624 KB Output is correct

Subtask #4
0 / 20.0

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