oj.uz

Submission #1031896

# Submission time Handle Problem Language Result Execution time Memory
1031896 2024-07-23T08:31:01 Z stdfloat Street Lamps (APIO19_street_lamps) C++17
20 / 100
 206 ms 13484 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

vector<int> st;

int upd(int nd, int l, int r, int x, int vl) {
    if (r < x || x < l) return st[nd];

    if (l == r) return st[nd] = vl;

    int ch = (nd << 1) + 1, md = (l + r) >> 1;
    return st[nd] = max(upd(ch, l, md, x, vl), upd(ch + 1, md + 1, r, x, vl));
}

int fnd(int nd, int l, int r, int x, int y) {
    if (r < x || y < l) return 0;

    if (x <= l && r <= y) return st[nd];

    int ch = (nd << 1) + 1, md = (l + r) >> 1;
    return max(fnd(ch, l, md, x, y), fnd(ch + 1, md + 1, r, x, y));
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);

    int n, q;
    string s;
    cin >> n >> q >> s;

    st.assign(n << 2, INT_MAX);
    for (int i = 0; i < n; i++) {
        if (s[i] == '1') upd(0, 0, n - 1, i, 0);
    }

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

        if (t == "toggle") {
            int i;
            cin >> i; i--;
    
            upd(0, 0, n - 1, i, z);
        }
        else {
            int a, b;
            cin >> a >> b; a--; b--;
        
            cout << z - min(z, fnd(0, 0, n - 1, a, b - 1)) << '\n';
        }
    }
}

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 99 ms 4132 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 472 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 96 ms 9776 KB Output is correct
6 Correct 144 ms 10468 KB Output is correct
7 Correct 163 ms 10980 KB Output is correct
8 Correct 201 ms 13484 KB Output is correct
9 Correct 60 ms 4076 KB Output is correct
10 Correct 70 ms 4272 KB Output is correct
11 Correct 71 ms 4540 KB Output is correct
12 Correct 157 ms 12096 KB Output is correct
13 Correct 206 ms 13476 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 -