Submission #440498

#	Time	Username	Problem	Language	Result	Execution time	Memory
440498		den_tar	Bridges (APIO19_bridges)	C++14	29 / 100	3067 ms	10416 KiB

bridges

#include <bits/stdc++.h>

using namespace std;

#define fast ios_base::sync_with_stdio();cin.tie();cout.tie();
#define en cout<<endl;
#define ops cout<<"ops"<<endl;
#define line cout<<"---------------------------"<<endl;
#define fi first
#define se second

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pllll;
typedef string str;

const ll DIM = 1e5 + 7;
const ll DIMM = 5e4 + 7;
const ll DDIM = 7;
const ll INF = 1e18 + 7;
const ll X = 1e5 + 7;
const ll BS = 2e5 + 7;
const ll AS = 26 + 7;
const ll MODULO = 1e9 + 7;

ll nt,n,m,k,q;

ll fl;

ll val,val1;

ll v1,v2;

ll d[DIM],vis[DIM];

vector<pllll> a[DIM];

ll type,x,y;

ll res;















void clearvis(){
    for(int i=1;i<=n;i++)vis[i]=0;

    return;
}

void dfs(ll v,ll w){

    res++;
    vis[v]=1;

    for(auto to:a[v]){
     if(vis[to.fi]==1 || d[to.se]<w)continue;
     dfs(to.fi,w);
    }

    return;
}

void solve1(){
    cin>>k;

    for(int qq=1;qq<=k;qq++){
     cin>>type>>x>>y;

     if(type==1)d[x]=y;
     else{
      clearvis();
      res=0;
      dfs(x,y);
      cout<<res<<endl;
     }
    }

    return;
}














ll t[4*DIM];

ll l1,r1,l2,r2,mid;


void btree(ll v,ll tl,ll tr){

    if(tl==tr){
     t[v]=d[tl];
     return;
    }

    ll tm=(tl+tr)/2;

    btree(2*v+1,tl,tm);
    btree(2*v+2,tm+1,tr);

    t[v]=min(t[2*v+1],t[2*v+2]);

    return;
}

void up(ll v,ll tl,ll tr,ll p,ll val){

    if(tr<p || p<tl)return;

    if(tl==tr){
     t[v]=val;
     return;
    }

    ll tm=(tl+tr)/2;

    up(2*v+1,tl,tm,p,val);
    up(2*v+2,tm+1,tr,p,val);

    t[v]=min(t[2*v+1],t[2*v+2]);

    return;
}

ll f(ll v,ll tl,ll tr,ll l,ll r){

    if(tr<l || r<tl)return INF;

    if(l<=tl && tr<=r)return t[v];

    ll tm=(tl+tr)/2;

    return min(f(2*v+1,tl,tm,l,r),f(2*v+2,tm+1,tr,l,r));
}

void solve2(){

    btree(0,1,m);

    cin>>k;

    for(int qq=1;qq<=k;qq++){
     cin>>type>>x>>y;

     if(type==1){
      up(0,1,m,x,y);
      d[x]=y;
     }
     else{

      l1=1;r1=x-1;
      while(l1<r1){
       mid=(l1+r1)/2;
       if(f(0,1,m,mid,x-1)<y)l1=mid+1;
       else r1=mid;
      }

      l2=x;r2=m;
      while(l2<r2){
       mid=(l2+r2+1)/2;
       if(f(0,1,m,x,mid)<y)r2=mid-1;
       else l2=mid;
      }

      if(d[l2]>=y)l2++;
      if(d[r1]<y)r1++;

      res=l2-r1+1;

      cout<<res<<endl;
     }
    }
    return;
}


void solve3(){

    cin>>k;

    for(int qq=1;qq<=k;qq++){
     cin>>type>>x>>y;
     cout<<1<<endl;
    }
    return;
}

int main()
{
    fast;
    //ll x1,y1,x2,y2;

    cin>>n>>m;

    if(m!=(n-1))fl=1;

    for(int i=1;i<=m;i++){
     cin>>v1>>v2>>d[i];

     if(v1!=i || v2!=(i+1))fl=1;

     a[v1].push_back({v2,i});
     a[v2].push_back({v1,i});
    }

    if(m==0){
     solve3();
     return 0;
    }

    if(fl==0){
     solve2();
     return 0;
    }

    solve1();

    return 0;
}

/*
8 7
1 2 9
2 3 1
3 4 9
4 5 9
5 6 9
6 7 1
7 8 9
11
2 4 2
2 8 2
2 1 2
1 2 9
2 4 2
2 8 2
2 1 2
1 6 9
2 4 2
2 8 2
2 1 2
*/

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