oj.uz

답안 #406697

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
406697 2021-05-18T03:13:07 Z tengiz05 가로등 (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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 80 ms 824 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -