Submission #721879

#	Time	Username	Problem	Language	Result	Execution time	Memory
721879		GrandTiger1729	Bridges (APIO19_bridges)	C++17	0 / 100	640 ms	524288 KiB

bridges

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;
struct SegTree {
    int l, r, mid;
    int val = INF;
    SegTree *lc, *rc;
    SegTree(int _l, int _r): l(_l), r(_r){
        mid = (l + r) / 2;
        if (l == r - 1) return;
        lc = new SegTree(l, mid);
        rc = new SegTree(mid, r);
    }
    void pull(){
        val = min(lc->val, rc->val);
    }
    void update(int i, int u){
        if (l == r - 1)
            return void(val = u);
        if (i < mid)
            lc->update(i, u);
        else
            rc->update(i, u);
        pull();
    }
    int query(int ll, int rr){
        if (ll == rr) return -INF;
        if (ll <= l && rr >= r)
            return val;
        int ret = INF;
        if (ll < mid)
            ret = min(ret, lc->query(ll, rr));
        if (mid < rr)
            ret = min(ret, rc->query(ll, rr));
        return ret;
    }
};

int main(){
    cin.tie(0)->sync_with_stdio(0);
    int n, m; cin >> n >> m;
    SegTree st(0, m);
    for (int i = 0; i < m; i++){
        int u, v, w; cin >> u >> v >> w;
        u--, v--;
        st.update(i, w);
    }
    int q; cin >> q;
    while (q--){
        int t; cin >> t;
        if (t == 1){
            int i, w; cin >> i >> w;
            i--;
            st.update(i, w);
        }else{
            int u, w; cin >> u >> w;
            u--;
            int ans = 0;
            {
                int l = u, r = n;
                while (l < r - 1){
                    int mid = (l + r) / 2;
                    if (st.query(u, mid) < w)
                        r = mid;
                    else
                        l = mid;
                }
                ans += l - u;
            }
            {
                int l = -1, r = u;
                while (l < r - 1){
                    int mid = (l + r + 1) / 2;
                    if (st.query(mid, u) < w)
                        l = mid;
                    else
                        r = mid;
                }
                ans += u - r;
            }
            cout << ans + 1 << '\n';
        }
    }
    return 0;
}

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