Submission #955508

#	Time	Username	Problem	Language	Result	Execution time	Memory
955508		bunhadasou	Bridges (APIO19_bridges)	C++14	16 / 100	611 ms	8612 KiB

bridges

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define PB push_back
#define EB emplace_back
#define bit(n,i) ((n>>i)&1)
#define all(x) x.begin(),x.end()
#define ll long long
#define sz(x) (int)x.size()
#define TASK "cf"

using namespace std;



const int maxn=1e5+5;
int T[2][4*maxn];
pair<pair<int,int>,int> ds[maxn];
int n,m,q;



void update(int rev,int node,int l,int r,int u,int v,int val) {
    if (u>r|| v<l) return ;
    if (u<=l&& r<=v) {
        T[rev][node]=val; return ;
    }
    int mid=l+r>>1;
    update(rev,node<<1,l,mid,u,v,val);
    update(rev,node<<1|1,mid+1,r,u,v,val);
    T[rev][node]=min(T[rev][node<<1],T[rev][node<<1|1]);
}

int get(int rev,int node,int l,int r,int u,int v) {
    if (u>r||v<l) return 1e9+9;
    if (u<=l&&r<=v) return T[rev][node];
    int mid=l+r>>1;
    return min(get(rev,node<<1,l,mid,u,v),get(rev,node<<1|1,mid+1,r,u,v));
}

int tim1(int pos,int val) {
    int lo=1,hi=pos-1;
    if (hi<lo || hi<1) return pos;
    int res=pos;
    while(hi-lo>=0){
        int mid=hi+lo>>1;
        if (get(0,1,1,n,mid,pos-1)>=val){
            res=mid;
            hi=mid-1;
        }
        else lo=mid+1;
    }
    return res;
}

int tim2(int pos,int val) {
    int lo=pos+1,hi=n;
    if (hi<lo || lo>n) return pos;
    int res=pos;
    while(hi-lo>=0){
        int mid=hi+lo>>1;
        if (get(1,1,1,n,pos+1,mid)>=val){
            res=mid;
            lo=mid+1;
        }
        else hi=mid-1;
    }
    return res;
}




signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 
    cin>>n>>m;
    for (int i=1;i<=m;i++) {
        int x,y,z;cin>>x>>y>>z;
        ds[i]=mp(mp(x,y),z);
    }
    for (int i=1;i<=m;i++) {
        int u=ds[i].fi.fi,v=ds[i].fi.se,w=ds[i].se;
        update(0,1,1,n,u,u,w);
        update(1,1,1,n,v,v,w);
    }
    cin>>q;
    while(q--) {
        int type,x,y; cin>>type>>x>>y;
        if (type==1){
            int u=ds[x].fi.fi,v=ds[x].fi.se;
            ds[x].se=y;
            update(0,1,1,n,u,u,y);
            update(1,1,1,n,v,v,y);
        }
        else {
            int lo=tim1(x,y),hi=tim2(x,y);
            cout<<hi-lo+1<<"\n";
        }
    }


    return 0;

}

Compilation message (stderr)

bridges.cpp: In function 'void update(int, int, int, int, int, int, int)':
bridges.cpp:29:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |     int mid=l+r>>1;
      |             ~^~
bridges.cpp: In function 'int get(int, int, int, int, int, int)':
bridges.cpp:38:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |     int mid=l+r>>1;
      |             ~^~
bridges.cpp: In function 'int tim1(int, int)':
bridges.cpp:47:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |         int mid=hi+lo>>1;
      |                 ~~^~~
bridges.cpp: In function 'int tim2(int, int)':
bridges.cpp:62:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   62 |         int mid=hi+lo>>1;
      |                 ~~^~~

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