Submission #893528

#	Time	Username	Problem	Language	Result	Execution time	Memory
893528		Warinchai	Bridges (APIO19_bridges)	C++14	16 / 100	691 ms	8028 KiB

bridges

#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int> >v[100005];
int w[100005];
int vis[100005];
struct segtree{
    int info[400005];
    void upd(int st,int en,int i,int pos,int val){
        if(st>pos||en<pos)return;
        if(st==en)return void(info[i]=val);
        int m=(st+en)/2;
        upd(st,m,i*2,pos,val);
        upd(m+1,en,i*2+1,pos,val);
        info[i]=min(info[i*2],info[i*2+1]);
    }
    int fmin(int st,int en,int i,int l,int r){
        if(st>r||en<l)return INT_MAX;
        if(st>=l&&en<=r)return info[i];
        int m=(st+en)/2;
        return min(fmin(st,m,i*2,l,r),fmin(m+1,en,i*2+1,l,r));
    }
}tr;
/*int dfs(int x,int wc){
    vis[x]=1;
    int sz=1;
    for(auto e:v[x]){
        if(w[e.second]>=wc&&vis[e.first]==0){
            sz+=dfs(e.first,wc);
        }
    }
    return sz;
}*/
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        tr.upd(1,n,1,i,c);
    }
    int q;
    cin>>q;
    while(q--){
        int t;
        cin>>t;
        if(t==1){
            int x,r;
            cin>>x>>r;
            tr.upd(1,n,1,x,r);
        }else{
            int s,w;
            cin>>s>>w;
            //cout<<dfs(s,w)<<"\n";
            int rans=1;
            int st,en,ans;
            st=1,en=s-1,ans=s;
            while(st<=en){
                int m=(st+en)/2;
                if(tr.fmin(1,n,1,m,s-1)>=w){
                    ans=m;
                    en=m-1;
                }else{
                    st=m+1;
                }
            }
            rans+=s-ans;
            st=s,en=n-1,ans=s-1;
            while(st<=en){
                int m=(st+en)/2;
                if(tr.fmin(1,n,1,s,m)>=w){
                    ans=m;
                    st=m+1;
                }else{
                    en=m-1;
                }
            }
            rans+=ans+1-s;
            cout<<rans<<"\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