Submission #597545

#	Time	Username	Problem	Language	Result	Execution time	Memory
597545		WongChun1234	Bridges (APIO19_bridges)	C++14	16 / 100	799 ms	9460 KiB

bridges

#include<bits/stdc++.h>
using namespace std;
const int N=150050;
int n,m,q,u[N],v[N],w[N],ans,t,a,b,seg[N<<2];
bool vis[N];
vector<int> adj[N];
void build(int id,int l,int r){
	if (l==r){
		seg[id]=w[l];
		return;
	}
	int mid=(l+r)/2;
	build(id*2,l,mid);
	build(id*2+1,mid+1,r);
	seg[id]=min(seg[id*2],seg[id*2+1]);
}
void modify(int id,int l,int r,int ql,int val){
	if (l>ql||r<ql) return;
	if (l==r){
		seg[id]=val;
		return;
	}
	int mid=(l+r)/2;
	modify(id*2,l,mid,ql,val);
	modify(id*2+1,mid+1,r,ql,val);
	seg[id]=min(seg[id*2],seg[id*2+1]);
}
int query(int id,int l,int r,int ql,int qr){
	if (l>qr||r<ql) return INT_MAX;
	if (l>=ql&&r<=qr) return seg[id];
	int mid=(l+r)/2;
	return min(query(id*2,l,mid,ql,qr),query(id*2+1,mid+1,r,ql,qr));
}
int main(){
	cin>>n>>m;
	for (int i=1;i<=m;i++){
		cin>>u[i]>>v[i]>>w[i];
		adj[u[i]].push_back(i);
		adj[v[i]].push_back(-i);
	}
	if (m) build(1,1,m);
	cin>>q;
	while (q--){
		cin>>t>>a>>b;
		if (t==1){
			w[a]=b;
			modify(1,1,m,a,b);
			continue;
		}
		if (!m){
			cout<<"1\n";
			continue;
		}
		int ll,rr,mm,currl;
		ll=1,rr=a-1;
		if (w[a-1]<b){
			currl=a;
			goto skip;
		}
		while (ll<rr){
			mm=(ll+rr)/2;
			if (query(1,1,m,mm,a-1)>=b) rr=mm;
			else ll=mm+1;
		}
		currl=rr;
		skip:;
		ll=a,rr=m;
		if (w[a]<b){
			cout<<a-currl+1<<"\n";
			continue;
		}
		while (ll<rr){
			mm=(ll+rr+1)/2;
			if (query(1,1,m,a,mm)>=b) ll=mm;
			else rr=mm-1;
		}
		cout<<ll-currl+2<<"\n";
	}
}

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