Submission #1031717

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031717		stdfloat	Bridges (APIO19_bridges)	C++17	16 / 100	513 ms	4048 KiB

bridges

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

using ll = long long;

#define sz(v) (int)(v).size()

#define ff  first
#define ss  second
#define pii pair<int, int>

vector<int> st;

int upd(int nd, int l, int r, int x, int vl) {
    if (r < x || x < l) return st[nd];

    if (l == r) return st[nd] = vl;

    int ch = nd << 1, md = (l + r) >> 1;
    return st[nd] = min(upd(ch, l, md, x, vl), upd(ch + 1, md + 1, r, x, vl));
}

int fnd(int nd, int l, int r, int x, int y) {
    if (r < x || y < l) return INT_MAX;

    if (x <= l && r <= y) return st[nd];

    int ch = nd << 1, md = (l + r) >> 1;
    return min(fnd(ch, l, md, x, y), fnd(ch + 1, md + 1, r, x, y));
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    st.assign(n << 2, INT_MAX);
    for (int i = 1; i < n; i++) {
        int x, y, d;
        cin >> x >> y >> d;

        assert(x == i && y == i + 1);

        upd(1, 1, n, i, d);
    }

    int q;
    cin >> q;
    while (q--) {
        int t;
        cin >> t;

        if (t == 1) {
            int b, r;
            cin >> b >> r;
        
            upd(1, 1, n, b, r);
        }
        else {
            int s, w;
            cin >> s >> w;

            int l = 1, r = s - 1;
            while (l <= r) {
                int md = (l + r) >> 1;

                if (fnd(1, 1, n, md, s - 1) < w) l = md + 1;
                else r = md - 1;
            }

            int ans = s - l + 1;
        
            l = s, r = n - 1;
            while (l <= r) {
                int md = (l + r) >> 1;

                if (w <= fnd(1, 1, n, s, md)) l = md + 1;
                else r = md - 1;
            }

            cout << ans + l - s << endl;
        }
    }
}

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