Submission #934030

#	Time	Username	Problem	Language	Result	Execution time	Memory
934030		vjudge1	Bridges (APIO19_bridges)	C++17	16 / 100	461 ms	4156 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;

const ll IDEM = 1E18+16;

#define mid ((l+r)>>1)
#define off (2*(mid-l+1))
struct SegTree {
    vll tree;
    ll n;

    SegTree (ll n): tree(2*n, IDEM), n(n) {}

    void pull (ll l, ll r, ll id) {
        tree[id] = min(tree[id+1], tree[id+off]);
    }

    void update (ll at, ll val, ll l, ll r, ll id) {
        if (at < l || r < at) return;
        if (at <= l && r <= at) {
            tree[id]=val;
            return;
        }
        update(at, val, l, mid, id+1);
        update(at, val, mid+1, r, id+off);
        pull(l, r, id);
    }

    void update (ll at, ll val) {
        update(at, val, 0, n-1, 0);
    }

    ll query (ll ql, ll qr, ll l, ll r, ll id) {
        if (qr < l || r < ql) return IDEM;
        if (ql <= l && r <= qr) return tree[id];
        return min(query(ql, qr, l, mid, id+1), query(ql, qr, mid+1, r, id+off));
    }

    ll query (ll ql, ll qr) {
        return query(ql, qr, 0, n-1, 0);
    }
};

int main () {
    cin.tie(nullptr) -> sync_with_stdio(false);
    ll n, m;
    cin >> n >> m;
    SegTree st(m);
    for (ll i = 0; i < m; i++) {
        ll u, v, w;
        cin >> u >> v >> w;
        u--; v--;
        st.update(i, w);
    }
    ll Q;
    cin >> Q;
    while (Q--) {
        char type;
        cin >> type;
        switch (type) {
            case '1':
            {ll i, w;
            cin >> i >> w;
            i--;
            st.update(i, w);}
            break;
            case '2':
            {ll u, w;
            cin >> u >> w;
            u--;
            ll ans=1;
            if (u>0 && st.query(u-1, u-1) >= w) { // to the left
                ll l=-1, r=u-1;
                while (l+1 < r) {
                    ll midBS = (l+r)>>1;
                    ll ww = st.query(midBS, r);
                    if (ww < w) {
                        l = midBS;
                    } else {
                        r = midBS;
                    }
                }
                ans += u-r;
            }
            if (u<m && st.query(u, u) >= w) {
                ll l=u, r=m;
                while (l+1 < r) {
                    ll midBS = (l+r)>>1;
                    ll ww = st.query(l, midBS);
                    if (ww < w) {
                        r = midBS;
                    } else {
                        l = midBS;
                    }
                }
                ans += l-u+1;
            }
            cout << ans << '\n';
            }
            break;
        }
    }
    return 0;
}

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