Submission #926341

#	Time	Username	Problem	Language	Result	Execution time	Memory
926341		TAhmed33	Bridges (APIO19_bridges)	C++98	0 / 100	683 ms	1364 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
#define mid ((l + r) >> 1)
#define tl (node + 1)
#define tr (node + 2 * (mid - l + 1))
const int MAXN = 1e5 + 25;
struct SegmentTree {
    int tree[MAXN << 1];
    void update (int l, int r, int a, int b, int node) {
        if (l > a || r < a) return;
        if (l == r) {
            tree[node] = b; return;
        }
        update(l, mid, a, b, tl); update(mid + 1, r, a, b, tr);
        tree[node] = min(tree[tl], tree[tr]);
    }
    int get (int l, int r, int a, int b, int node) {
        if (l > b || r < a) return (int)1e9;
        if (l >= a && r <= b) return tree[node];
        return min(get(l, mid, a, b, tl), get(mid + 1, r, a, b, tr));
    }
} cur;
int main () {
    int n, m;
    cin >> n >> m;
    while (m--) {
        int a, b, c; cin >> a >> b >> c; if (a > b) swap(a, b);
        cur.update(1, n - 1, a, c, 1);
    }
    int q; cin >> q;
    while (q--) {
        int t; cin >> t;
        if (t == 1) {
            int a, b; cin >> a >> b;
            cur.update(1, n, a, b, 1);
        } else {
            int a, b; cin >> a >> b;
            int l = a, r = n - 1, ans = -1; int sum = 1;
            while (l <= r) {
                if (cur.get(1, n - 1, a, mid, 1) < b) {
                    r = mid - 1; 
                } else {
                    ans = mid; l = mid + 1; 
                }
            }
            if (ans != -1) sum += ans - a + 1;
            l = 1, r = a - 1, ans = -1;
            while (l <= r) {
                if (cur.get(1, n - 1, mid, a - 1, 1) < b) {
                    l = mid + 1;
                } else {
                    ans = mid; r = mid - 1;
                }
            }
            if (ans != -1) sum += a - ans;
            cout << sum << '\n';
        }
    }
}

• Subtask 1: 0 / 13
• Subtask 2: 0 / 16
• Subtask 3: 0 / 17
• Subtask 4: 0 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27