Submission #655107

#	Time	Username	Problem	Language	Result	Execution time	Memory
655107		DeMen100ns	Bridges (APIO19_bridges)	C++17	16 / 100	746 ms	3844 KiB

bridges

/*
Author : DeMen100ns (a.k.a Vo Khac Trieu)
School : VNU-HCM High school for the Gifted
fuck you adhoc
*/

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;
const long long INF = 1e18 + 7;
const int MAXA = 1e9;
const int B = sqrt(N) + 5;

int n, m, q;
int seg[4 * N];

void upd(int id, int l, int r, int pos, int val){
    if (l == r){
        seg[id] = val;
        return;
    }
    int mid = (l + r) >> 1;
    if (pos <= mid){
        upd(id << 1, l, mid, pos, val);
    } else {
        upd(id << 1 | 1, mid + 1, r, pos, val);
    }
    seg[id] = min(seg[id << 1], seg[id << 1 | 1]);
}

int get(int id, int l, int r, int u, int v){
    if (l > v || r < u) return MAXA;
    if (l >= u && r <= v) return seg[id];

    int mid = (l + r) >> 1;
    int v1 = get(id << 1, l, mid, u, v);
    int v2 = get(id << 1 | 1, mid + 1, r, u, v);

    return min(v1, v2);
}

void solve()
{
    cin >> n >> m;
    for(int i = 1; i <= m; ++i){
        int u, v, w; cin >> u >> v >> w;
        //a[i] = w;
        upd(1, 0, n, i, w);
    }

    cin >> q;
    while (q--){
        int type, u, val; cin >> type >> u >> val;
        if (type == 1){
            upd(1, 0, n, u, val);
        } else{
            int ll = -1, rl = u;
            while (ll + 1 < rl){
                int mid = (ll + rl) >> 1;
                if (get(1, 0, n, mid, u - 1) >= val) rl = mid;
                else ll = mid;
            }
            int l = rl;

            int lr = u - 1, rr = n;
            while (lr + 1 < rr){
                int mid = (lr + rr) >> 1;
                if (get(1, 0, n, u, mid) >= val) lr = mid;
                else rr = mid;
            }
            int r = lr;

            cout << r - l + 2 << endl;
        }
        //for(int i = 1; i < n; ++i) cout << get(1, 0, n, i, i) << " ";
        //cout << endl;
    }
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    // freopen("codeforces.inp","r",stdin);
    // freopen("codeforces.out","w",stdout);

    int t = 1; // cin >> t;
    while (t--)
    {
        solve();
    }
}

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