oj.uz

Submission #985225

# Submission time Handle Problem Language Result Execution time Memory
985225 2024-05-17T13:13:17 Z nnin Street Lamps (APIO19_street_lamps) C++14
20 / 100
 214 ms 13084 KB 
#include<bits/stdc++.h>
using namespace std;

int n, q;

int seg[1200005];
void build(int i, int l, int r) {
    seg[i] = 1e9;
    if(l==r) return;
    int m = (l+r)/2;
    build(i*2+1, l, m);
    build(i*2+2, m+1, r);

}
void update(int i, int l, int r, int x, int val) {
    if(l==r) {
        seg[i] = val;
        return;
    }
    int m = (l+r)/2;
    if(x<=m) update(i*2+1, l, m, x, val);
    else update(i*2+2, m+1, r, x, val);
    seg[i] = max(seg[i*2+1], seg[i*2+2]);
}
int query(int i, int l, int r, int wl, int wr) {
    if(wl>r || wr<l) return 0;
    if(wl<=l && wr>=r) return seg[i];
    int m = (l+r)/2;
    return max(query(i*2+1, l, m, wl, wr), query(i*2+2, m+1, r, wl, wr));
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin>>n>>q;
    string s;
    cin>>s;
    build(0, 0, n-1);
    for(int i=0;i<n;i++) {
        if(s[i]-'0'==1) update(0, 0, n-1, i, 0);
    }
    for(int i=1;i<=q;i++) {
        cin>>s;
        if(s[0]=='q') {
            int a, b;
            cin>>a>>b;
            a--; b--;
            int q = query(0, 0, n-1, a, b-1);
            if(q==1e9) cout<<0<<'\n';
            else cout<<i-q<<'\n';
        } else {
            int a;
            cin>>a;
            a--;
            update(0, 0, n-1, a, i);
        }
    }
}

/*
5 7
11011
query 1 2
query 1 2
query 1 6
query 3 4
toggle 3
query 3 4
query 1 6
*/

Subtask #1
0 / 20.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 64 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 344 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 504 KB Output is correct
5 Correct 105 ms 9360 KB Output is correct
6 Correct 119 ms 9952 KB Output is correct
7 Correct 178 ms 10724 KB Output is correct
8 Correct 214 ms 13084 KB Output is correct
9 Correct 85 ms 3964 KB Output is correct
10 Correct 75 ms 4176 KB Output is correct
11 Correct 91 ms 4852 KB Output is correct
12 Correct 186 ms 11640 KB Output is correct
13 Correct 213 ms 13084 KB Output is correct

Subtask #4
0 / 20.0

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