Submission #262739

#	Time	Username	Problem	Language	Result	Execution time	Memory
262739		dsjong	Bridges (APIO19_bridges)	C++14	0 / 100	548 ms	4236 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
int a[50005], seg[200005];
void build(int L, int R, int node){
	if(L==R){
		seg[node]=a[L];
		return;
	}
	int M=(L+R)/2;
	build(L, M, 2*node);
	build(M+1, R, 2*node+1);
	seg[node]=min(seg[2*node], seg[2*node+1]);
}
int query(int a, int b, int L, int R, int node){
	if(L>R) return -1;
	if(b<L || a>R) return -1;
	if(a<=L && R<=b) return seg[node];
	int M=(L+R)/2;
	return min(query(a, b, L, M, 2*node), query(a, b, M+1, R, 2*node+1));
}
void update(int a, int v, int L, int R, int node){
	if(a<L || a>R) return;
	if(L==R){
		seg[node]=v;
		return;
	}
	int M=(L+R)/2;
	update(a, v, L, M, 2*node);
	update(a, v, M+1, R, 2*node+1);
	seg[node]=min(seg[2*node], seg[2*node+1]);
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n, m;
	cin>>n>>m;
	for(int i=1;i<n;i++){
		int u, v;
		cin>>u>>v>>a[i];
	}
	build(1, n, 1);
	int q;
	cin>>q;
	while(q--){
		int t, x, y;
		cin>>t>>x>>y;
		if(t==1){
			update(x, y, 1, n, 1);
		}
		else{
			int ans1, ans2;
			int L=x-1, R=n-1;
			while(L<R){
				int M=(L+R+1)/2;
				if(query(x, M, 1, n, 1) > y) R=M-1;
				else L=M;
			}
			ans1=L;
			L=1, R=x;
			while(L<R){
				int M=(L+R)/2;
				if(query(M, x-1, 1, n, 1) > y) L=M+1;
				else R=M;
			}
			ans2=L;
			cout<<ans1-ans2+1<<"\n";
		}
	}
}

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