Submission #267098

#	Time	Username	Problem	Language	Result	Execution time	Memory
267098		kimbj0709	Bridges (APIO19_bridges)	C++14	16 / 100	1059 ms	5660 KiB

bridges

#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define f first
#define s second
#define maxn 50050
vector<int> seg(maxn*8,INT_MAX);
void update(int node,int start,int end,int pos,int val){
    if(start==end){
        assert(start==pos);
        seg[node] = val;
        return;
    }
    int mid = (start+end)/2;
    if(pos<=mid){
        update(node*2+1,start,mid,pos,val);
    }
    else{
        update(node*2+2,mid+1,end,pos,val);
    }
    seg[node] = min(seg[node*2+1],seg[node*2+2]);
}
int query(int node,int start,int end,int rangemin,int rangemax){
    if(start>rangemax||end<rangemin){
        return INT_MAX;
    }
    if(start>=rangemin&&end<=rangemax){
        return seg[node];
    }
    int mid = (start+end)/2;
    return min(query(node*2+1,start,mid,rangemin,rangemax),query(node*2+2,mid+1,end,rangemin,rangemax));
}
int32_t main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n,m,q;
    int input1,input2,input3;
    cin >> n >> m;
    vector<pair<int,pair<int,int> > > edges;
    for(int i=0;i<m;i++){
        cin >> input1 >> input2 >> input3;
        edges.push_back({input1,{input2,input3}});
        update(0,0,m-1,i,input3);
    }
    cin >> q;
    for(int i=0;i<q;i++){
        cin >> input1 >> input2 >> input3;
        if(input1==1){
            update(0,0,m-1,input2-1,input3);
        }
        else{
            int ans = 1;
            int lo = 0,hi = input2;
            if(lo==hi){
                goto cont1;
            }
            while(lo+1!=hi){
                int mid = (lo+hi)/2;
                assert(input2-2>=mid-1);
                if(query(0,0,m-1,mid-1,input2-2)>=input3){
                    hi = mid;
                }
                else{
                    lo = mid;
                }
            }
            ans += input2-hi;
            //cout << input2-hi << "--\n";
            cont1 : ;
            lo = input2,hi=n+1;
            if(lo==hi){
                goto cont2;
            }
            //cout << lo << " " << hi << endl;
            while(lo+1!=hi){
                int mid = (lo+hi)/2;
                assert(mid-2>=input2-1);
                if(query(0,0,m-1,input2-1,mid-2)>=input3){
                    lo = mid;
                }
                else{
                    hi = mid;
                }
            }
            ans += lo-input2;
            //cout << lo-input2 << "--\n";
            cont2 : ;
            cout << ans << "\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