Submission #1119034

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119034		PagodePaiva	Bridges (APIO19_bridges)	C++17	16 / 100	514 ms	3988 KiB

bridges

#include<bits/stdc++.h>

using namespace std;

const int N = 200010;
int v[N];

struct Segtree{
    int tree[4*N];
    int join(int a, int b){
        return min(a, b);
    }
    void build(int node, int l, int r){
        if(l == r){
            tree[node] = v[l];
            return;
        }
        int mid = (l+r)/2;
        build(2*node, l, mid);
        build(2*node+1, mid+1, r);
        tree[node] = join(tree[2*node], tree[2*node+1]);
    }
    void update(int node, int l, int r, int pos, int val){
        if(l == r){
            tree[node] = val;
            return;
        }
        int mid = (l+r)/2;
        if(l <= pos and pos <= mid) update(2*node, l, mid, pos, val);
        else update(2*node+1, mid+1, r, pos, val);
        tree[node] = join(tree[2*node], tree[2*node+1]);
        return;
    }
    int query(int node, int l, int r, int tl, int tr){
        if(l > tr or tl > r) return 1e9+1;
        if(l <= tl and tr <= r) return tree[node];
        int mid = (tl+tr)/2;
        return join(query(2*node, l, r, tl,mid), query(2*node+1, l, r, mid+1, tr));
    }
} seg;

int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    int n, m;
    cin >> n >> m;
    for(int i = 0;i < m;i++){
        int a, b, w;
        cin >> a >> b >> w;
        v[i+1] = w;
    }
    if(n == 1){
        int q;
        cin >> q;
        while(q--){
            int a, b, c;
            cin >> a >> b >> c;
            cout << 1 << '\n';
        }
        return 0;
    }
    seg.build(1, 1, n-1);
    int q;
    cin >> q;
    while(q--){
        int t;
        cin >> t;
        if(t == 1){
            int s, w;
            cin >> s >> w;
            seg.update(1, 1, n-1, s, w);
        }
        else{
            int s, w;
            cin >> s >> w;
            int l = 1, r = s-1;
            int ans = s;
            while(l <= r){
                int mid = (l+r)/2;
                int val = seg.query(1, mid, s-1, 1, n-1);
                if(val < w){
                    l = mid+1;
                }
                else{
                    ans = mid;
                    r = mid-1;
                }
            }
            l = s;
            r = n-1;
            int ans2 = s;
            while(l <= r){
                int mid = (l+r)/2;
                int val = seg.query(1, s, mid, 1, n-1);
                if(val < w){
                    r = mid-1;
                }
                else{
                    ans2 = mid+1;
                    l = mid+1;
                }
            }
            cout << ans2-ans+1 << '\n';
        }
    }
}

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