Submission #729211

#	Time	Username	Problem	Language	Result	Execution time	Memory
729211		1075508020060209tc	Bridges (APIO19_bridges)	C++14	0 / 100	812 ms	6660 KiB

bridges

#include<bits/stdc++.h>

using namespace std;
#define int long long

int n;int m;int Q;
int ar[500005];

struct SGTR{
int l;int r;
int mn;
}tr[500006];

void buildtr(int nw,int l,int r){
tr[nw].l=l;tr[nw].r=r;
if(l==r){
    tr[nw].mn=ar[l];
    return;
}
int mi=(l+r)/2;
buildtr(nw*2,l,mi);
buildtr(nw*2+1,mi+1,r);
tr[nw].mn=min(tr[nw*2].mn,tr[nw*2+1].mn);
}

void upd(int nw,int pl,int val){
if(tr[nw].l==pl&&tr[nw].r==pl){
    tr[nw].mn=pl;
    return;
}
if(tr[nw].r<pl||tr[nw].l>pl){
    return;
}
upd(nw*2,pl,val);upd(nw*2+1,pl,val);
tr[nw].mn=min(tr[nw*2].mn,tr[nw*2+1].mn);
}

int qmn(int nw,int l,int r){
if(tr[nw].l>=l&&tr[nw].r<=r){
    return tr[nw].mn;
}
if(tr[nw].r<l||tr[nw].l>r){
    return 1e10;
}
return min(qmn(nw*2,l,r),qmn(nw*2+1,l,r));
}


signed main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
    int a;int b;
    cin>>a>>b>>ar[i];
}
buildtr(1,1,n-1);
cin>>Q;
while(Q--){
    int typ;
    cin>>typ;
    if(typ==1){
        int e;int v;
        cin>>e>>v;
        upd(1,e,v);
        ar[e]=v;
    }else{
    int a;int w;
    cin>>a>>w;

    int rit=a;

    while(rit+1<=n&&ar[rit]>=w){rit++;}
    int lit=a;
    while(lit-1>=1&&ar[lit-1]>=w){lit--;}
    cout<<rit-lit+1<<endl;
    continue;

    int l=1;int r=a;
    while(l<r){
        int mi=l+(r-l)/2;
        if(mi==a||qmn(1,mi,a-1)>=w){
            r=mi;
        }else{
            l=mi+1;
        }
    }
    int al=l;
    l=a;r=n;
    while(l<r){
        int mi=l+(r-l+1)/2;
        if(mi==a||qmn(1,a,mi-1)>=w){
            l=mi;
        }else{
            r=mi-1;
        }
    }
   // cout<<l<<" "<<al<<" ";
    cout<<l-al+1<<endl;
    }



}



}

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