oj.uz

Submission #721779

# Submission time Handle Problem Language Result Execution time Memory
721779 2023-04-11T07:14:15 Z GrandTiger1729 Street Lamps (APIO19_street_lamps) C++17
20 / 100
 503 ms 31044 KB 
#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;
struct SegTree {
    int l, r, mid;
    int val = INF;
    SegTree *lc, *rc;
    SegTree(int _l, int _r): l(_l), r(_r){
        mid = (l + r) / 2;
        if (l == r - 1) return;
        lc = new SegTree(l, mid);
        rc = new SegTree(mid, r);
    }
    void pull(){
        val = max(lc->val, rc->val);
    }
    void update(int i, int u){
        if (l == r - 1)
            return void(val = u);
        if (i < mid)
            lc->update(i, u);
        else
            rc->update(i, u);
        pull();
    }
    int query(int ll, int rr){
        if (ll <= l && rr >= r)
            return val;
        int ret = -INF;
        if (ll < mid)
            ret = max(ret, lc->query(ll, rr));
        if (mid < rr)
            ret = max(ret, rc->query(ll, rr));
        return ret;
    }
};

int main(){
    cin.tie(0)->sync_with_stdio(0);
    int n, q; cin >> n >> q;
    vector<bool> a(n);
    for (int i = 0; i < n; i++){
        char c; cin >> c;
        a[i] = c - '0';
    }
    SegTree st(0, n);
    for (int i = 0; i < n; i++)
        if (a[i])
            st.update(i, 0);
    for (int qq = 1; qq <= q; qq++){
        string ty; cin >> ty;
        if (ty == "toggle"){
            int i; cin >> i;
            i--;
            st.update(i, qq);
        }else{
            int l, r; cin >> l >> r;
            l--, r--;
            cout << max(0, qq - st.query(l, r)) << '\n';
        }
    }
    return 0;
}

Subtask #1
0 / 20.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 77 ms 1540 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 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 307 ms 29264 KB Output is correct
6 Correct 317 ms 29260 KB Output is correct
7 Correct 444 ms 29308 KB Output is correct
8 Correct 463 ms 31044 KB Output is correct
9 Correct 77 ms 1612 KB Output is correct
10 Correct 90 ms 1684 KB Output is correct
11 Correct 92 ms 1772 KB Output is correct
12 Correct 442 ms 29676 KB Output is correct
13 Correct 503 ms 30916 KB Output is correct

Subtask #4
0 / 20.0

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

Subtask #5
0 / 20.0

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