Submission #1187233

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187233		inesfi	Bridges (APIO19_bridges)	C++20	16 / 100	313 ms	2232 KiB

bridges

#include<bits/stdc++.h>
using namespace std;

#define endl "\n"
#define int long long

const int TAILLEMAXI=(1<<18),DECA=(1<<17);
int arbre[TAILLEMAXI];

int mini(int a,int b){
    if (a>b){
        return 1000*1000*1000+2;
    }
    if (a==b){
        return arbre[a];
    }
    if (a%2==1){
        return min(arbre[a],mini(a+1,b));
    }
    if (b%2==0){
        return min(arbre[b],mini(a,b-1));
    }
    return mini(a/2,b/2);
}

void change(int a){
    while (a>1){
        a/=2;
        arbre[a]=min(arbre[2*a],arbre[2*a+1]);
    }
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int nbnoeuds,nbaretes;
    cin>>nbnoeuds>>nbaretes;
    for (int i=0;i<nbaretes;i++){
        int a,b,p;
        cin>>a>>b>>p;
        arbre[DECA+i]=p;
        change(DECA+i);
    }
    int nbquest;
    cin>>nbquest;
    for (int i=0;i<nbquest;i++){
        int type;
        cin>>type;
        if (type==1){
            int endroit,val;
            cin>>endroit>>val;
            endroit--;
            arbre[DECA+endroit]=val;
            change(DECA+endroit);
        }
        else {
            int pos,poidsmax;
            cin>>pos>>poidsmax;
            pos--;
            int deb=pos,fin=0;
            while (deb>fin){
                int milieu=(deb+fin)/2;
                //cout<<milieu<<" ";
                if (mini(DECA+milieu,DECA+pos-1)>=poidsmax){
                    deb=milieu;
                    //cout<<"OUI"<<endl;
                }
                else {
                    fin=milieu+1;
                    //cout<<"NON"<<endl;
                }
            }
            int r=pos-deb+1;
            deb=pos,fin=nbnoeuds-1;
            while (deb<fin){
                int milieu=(deb+fin+1)/2;
                //cout<<milieu<<" ";
                if (mini(DECA+pos,DECA+milieu-1)>=poidsmax){
                    deb=milieu;
                    //cout<<"OUI"<<endl;
                }
                else {
                    fin=milieu-1;
                    //cout<<"NON"<<endl;
                }
            }
            //cout<<deb<<endl;
            r+=deb-pos;
            cout<<r<<endl;
        }
    }
    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