Submission #721826

#	Time	Username	Problem	Language	Result	Execution time	Memory
721826		alvingogo	Bridges (APIO19_bridges)	C++14	16 / 100	494 ms	3384 KiB

bridges

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

struct ST{
    vector<int> st;
    void init(int x){
        st.resize(4*x);
    }
    void update(int v,int L,int R,int p,int k){
        if(L==R){
            st[v]=k;
            return;
        }
        int m=(L+R)/2;
        if(p<=m){
            update(2*v+1,L,m,p,k);
        }
        else{
            update(2*v+2,m+1,R,p,k);
        }
        st[v]=min(st[2*v+1],st[2*v+2]);
    }
    int query(int v,int L,int R,int l,int r){
        if(L==l && r==R){
            return st[v];
        }
        int m=(L+R)/2;
        if(r<=m){
            return query(2*v+1,L,m,l,r);
        }
        else if(l>m){
            return query(2*v+2,m+1,R,l,r);
        }
        else{
            return min(query(2*v+1,L,m,l,m),query(2*v+2,m+1,R,m+1,r));
        }
    }
}st;
int main(){
    AquA;
    int n,m;
    cin >> n >> m;
    st.init(m);
    vector<pair<pair<int,int>,int> > e(m);
    for(int i=0;i<m;i++){
        cin >> e[i].fs.fs >> e[i].fs.sc >> e[i].sc;
        e[i].fs.fs--;
        e[i].fs.sc--;
        st.update(0,0,m-1,i,e[i].sc);
    }
    int q;
    cin >> q;
    for(int i=0;i<q;i++){
        int t;
        cin >> t;
        if(t==1){
            int a,b;
            cin >> a >> b;
            a--;
            st.update(0,0,m-1,a,b);
        }
        else{
            int a,b;
            cin >> a >> b;
            a--;
            int l=0,r=a;
            while(r>l){
                int mid=(l+r)/2;
                if(st.query(0,0,m-1,mid,a-1)>=b){
                    r=mid;
                }
                else{
                    l=mid+1;
                }
            }
            int fl=l;
            l=a-1;
            r=m-1;
            while(r>l){
                int mid=(l+r+1)/2;
                //cout << l << " " << r << " " << mid << '\n';
                if(st.query(0,0,m-1,a,mid)>=b){
                    l=mid;
                }
                else{
                    r=mid-1;
                }
            }
            int fr=l+1;
            cout << fr-fl+1 << "\n";
        }
    }
    return 0;
}

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