oj.uz

Submission #406697

# Submission time Handle Problem Language Result Execution time Memory
406697 2021-05-18T03:13:07 Z tengiz05 Street Lamps (APIO19_street_lamps) C++17
20 / 100
 188 ms 11012 KB 
#include <bits/stdc++.h>
struct segtree{
    std::vector<int> t;
    int n;
    segtree(int n, int v) : t(2 * n, v), n(n) { }
    int get(int l, int r){
        int res = -1;
        for (l += n, r += n; l <= r; l >>= 1, r >>= 1) {
            if (l & 1) res = std::max(res, t[l++]);
            if (!(r & 1)) res = std::max(res, t[r--]);
        }
        return res;
    }
    void update(int p, int val){
        for (t[p += n] = val; p > 1; p >>= 1) t[p >> 1] = std::max(t[p], t[p ^ 1]);
    }
};
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n, q;
    std::cin >> n >> q;
    std::string v;
    std::cin >> v;
    segtree s(n, 1e9);
    for (int i = 0; i < n; i++) {
        if (v[i] == '1') {
            s.update(i, -1);
        }
    }
    std::cout << '\n';
    for (int it = 0; it < q; it++) {
        std::string type;
        std::cin >> type;
        if (type == "query") {
            int l, r;
            std::cin >> l >> r;
            l--;
            r-=2;
            int res = it - s.get(l, r);
            std::cout << std::max(0, res) << '\n';
        } else {
            int p;
            std::cin >> p;
            p--;
            s.update(p, it);
        }
    }
}

Subtask #1
0 / 20.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 80 ms 824 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 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 80 ms 7280 KB Output is correct
6 Correct 117 ms 8024 KB Output is correct
7 Correct 151 ms 8748 KB Output is correct
8 Correct 188 ms 11008 KB Output is correct
9 Correct 93 ms 3908 KB Output is correct
10 Correct 101 ms 4244 KB Output is correct
11 Correct 101 ms 4472 KB Output is correct
12 Correct 173 ms 9556 KB Output is correct
13 Correct 186 ms 11012 KB Output is correct

Subtask #4
0 / 20.0

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