oj.uz

Submission #406920

# Submission time Handle Problem Language Result Execution time Memory
406920 2021-05-18T08:23:00 Z tengiz05 Bridges (APIO19_bridges) C++17
16 / 100
 338 ms 3480 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 = 1e9 + 7;
        for (l += n, r += n; l <= r; l >>= 1, r >>= 1) {
            if (l & 1) res = std::min(res, t[l++]);
            if (!(r & 1)) res = std::min(res, t[r--]);
        }
        return res;
    }
    void update(int p, int val){
        for (t[p += n] = val; p > 1; p >>= 1) t[p >> 1] = std::min(t[p], t[p ^ 1]);
    }
};
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n, m, q;
    std::cin >> n >> m;
    segtree seg(n + 2, 0);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        std::cin >> u >> v >> w;
        seg.update(i + 1, w);
    }
    std::cin >> q;
    while (q--) {
        int type;
        std::cin >> type;
        if (type == 1) {
            int b, r;
            std::cin >> b >> r;
            seg.update(b, r);
        } else {
            int s, W;
            std::cin >> s >> W;
            s--;
            int L, R;
            if (s == 0) L = 1;
            else {
                int l = -1, r = n + 1;
                while (l + 1 < r) {
                    int mid = (l + r) / 2;
                    if (seg.get(mid, s) >= W)
                        r = mid;
                    else 
                        l = mid;
                }
                L = r;
            }
            if (s == n - 1) R = n;
            else {
                int l = 0, r = n + 1;
                while (l + 1 < r) {
                    int mid = (l + r) / 2;
                    if (seg.get(s + 1, mid) >= W)
                        l = mid;
                    else 
                        r = mid;
                }
                R = l + 1;
            }
            std::cout << R - L + 1 << '\n';
        }
    }
}

Subtask #1
0 / 13.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
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 2696 KB Output is correct
2 Correct 121 ms 3128 KB Output is correct
3 Correct 124 ms 3280 KB Output is correct
4 Correct 131 ms 3108 KB Output is correct
5 Correct 121 ms 3012 KB Output is correct
6 Correct 221 ms 3232 KB Output is correct
7 Correct 235 ms 3252 KB Output is correct
8 Correct 208 ms 3252 KB Output is correct
9 Correct 41 ms 1844 KB Output is correct
10 Correct 187 ms 2472 KB Output is correct
11 Correct 148 ms 2480 KB Output is correct
12 Correct 338 ms 3480 KB Output is correct
13 Correct 86 ms 2996 KB Output is correct

Subtask #3
0 / 17.0

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

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 23 ms 2128 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 2696 KB Output is correct
2 Correct 121 ms 3128 KB Output is correct
3 Correct 124 ms 3280 KB Output is correct
4 Correct 131 ms 3108 KB Output is correct
5 Correct 121 ms 3012 KB Output is correct
6 Correct 221 ms 3232 KB Output is correct
7 Correct 235 ms 3252 KB Output is correct
8 Correct 208 ms 3252 KB Output is correct
9 Correct 41 ms 1844 KB Output is correct
10 Correct 187 ms 2472 KB Output is correct
11 Correct 148 ms 2480 KB Output is correct
12 Correct 338 ms 3480 KB Output is correct
13 Correct 86 ms 2996 KB Output is correct
14 Incorrect 88 ms 2372 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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