Submission #136739

#	Time	Username	Problem	Language	Result	Execution time	Memory
136739		KLPP	Bridges (APIO19_bridges)	C++14	13 / 100	878 ms	3564 KiB

bridges

#include<bits/stdc++.h>

using namespace std;
typedef long long int lld;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)
class ST{
  lld arr[200000];
  lld mid[200000];
public:
  void build(int a, int b, int node){
    if(a==b){
      arr[node]=0;
      return;
    }
    mid[node]=(a+b)/2;
    build(a,mid[node],2*node);
    build(mid[node]+1,b,2*node+1);
    arr[node]=min(arr[2*node],arr[2*node+1]);
    //delete(&mid);
  }
  void update(int a, int b, int node, int pos, lld val){
    if(pos<a || b<pos)return;
    if(a==b){
      arr[node]=val;
      return;
    }
    
    update(a,mid[node],2*node,pos,val);
    update(mid[node]+1,b,2*node+1,pos,val);
    arr[node]=min(arr[2*node],arr[2*node+1]);
    //delete(&mid);
  }
  lld query(int a, int b, int node, int x, int y){
    if(b<x || y<a)return 1000000000000;
    if(x<=a && b<=y)return arr[node];
    return min(query(a,mid[node],2*node,x,y),query(mid[node]+1,b,2*node+1,x,y));
  }
  
  void print(int a, int b, int node){
    cout<<a<<" "<<b<<" "<<arr[node]<<endl;
    if(a==b)return;
    int mid=(a+b)/2;
    print(a,mid,2*node);
    print(mid+1,b,2*node+1);
  }
};
int main(){
  
  int n,m,q;
  cin>>n>>m;
  ST S;
  lld edgelist[m][3];
  rep(i,0,m){
    rep(j,0,3){
      cin>>edgelist[i][j];
      if(j<2)edgelist[i][j]--;
    }
  }
  cin>>q;
  if(n<=1000 && m<=1000 && q<=10000){
    while(q--){
      int type;
      cin>>type;
      if(type==1){
	int num;
	lld val;
	cin>>num>>val;
	num--;
	edgelist[num][2]=val;
      }else{
	int start;
	lld w;
	cin>>start>>w;
	start--;
	vector<int> nei[n];
	bool visited[n];
	rep(i,0,n)visited[i]=false;
	//cout<<start<<endl;
	rep(i,0,m){
	  if(edgelist[i][2]>=w){
	    //cout<<edgelist[i][0]<<" "<<edgelist[i][1]<<endl;
	    nei[edgelist[i][0]].push_back(edgelist[i][1]);
	    nei[edgelist[i][1]].push_back(edgelist[i][0]);
	  }
	}
	queue<int> q;
	q.push(start);
	visited[start]=true;
	while(!q.empty()){
	  int u=q.front();q.pop();
	  trav(v,nei[u]){
	    if(!visited[v]){
	      visited[v]=true;
	      q.push(v);
	    }
	  }
	}
	lld ans=0;
	rep(i,0,n)ans+=visited[i];
	cout<<ans<<endl;
      }
    }
    return 0;
  }
  bool chain=(m==n-1);
  rep(i,0,m){
    if(edgelist[i][0]!=i || edgelist[i][1]!=i+1)chain=false;
  }
  int t,pos,start,hi,lo,mid;
  lld val,weight,ans;
  if(chain){
    S.build(0,n-2,1);
    rep(i,0,n-1){
      S.update(0,n-2,1,i,edgelist[i][2]);
    }
    while(q--){
      
      cin>>t;
      if(t==1){
	
	cin>>pos>>val;
	pos--;
	S.update(0,n-2,1,pos,val);
      }else{
	
	cin>>start>>weight;
	start--;
	ans=0;
	
	if(start>0){
	  hi=start;
	  lo=-1;
	  while(hi-lo>1){
	    int mid=(hi+lo)/2;
	    if(S.query(0,n-2,1,mid,start-1)<weight)lo=mid;
	    else hi=mid;
	  }
	  ans+=start-hi;
	}
	if(start<n-1){
	  
	  hi=n-1;
	  lo=start-1;
	  while(hi-lo>1){
	    mid=(hi+lo)/2;
	    if(S.query(0,n-2,1,start,mid)<weight)hi=mid;
	    else lo=mid;
	  }
	  ans+=lo-(start-1);
	}
	cout<<ans+1<<endl;
      }
    }
  }
  
  return 0;
}

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