Submission #558723

#	Time	Username	Problem	Language	Result	Execution time	Memory
558723		heavylightdecomp	Bridges (APIO19_bridges)	C++14	16 / 100	475 ms	3732 KiB

bridges

#include<bits/stdc++.h>
using namespace std;
const int mxN = 1<<16;
int st[2*mxN];
int n, m;
void update(int p, int v) {
	for(st[p += n] = v; p > 1; p >>= 1) st[p>>1] = min(st[p], st[p^1]);
}
//[l, r)
int query(int l, int r) {
	if(l >= r) return 1e9+1;
	int res = 1e9+1;
	for(l+=n,r+=n; l < r; l >>= 1, r >>= 1) {
		if(l&1) res = min(res, st[l++]);
		if(r&1) res = min(res, st[--r]);
	}
	return res;
}
signed main() {
	//freopen("bridge.in", "r", stdin);
	//freopen("bridge.out", "w", stdout);
	for(int i = 0; i < 2*mxN; i++) st[i] = 1e9+1;
	cin >> n >> m;
	if(m != n-1) exit(-1);
	for(int i = 1; i <= m; i++) {
		int u, v, d; cin >> u >> v >> d;
		u--, v--;
		update(u,d);
	}
	int q; cin >> q;
	for(int g = 0; g < q; g++) {
		int t; cin >> t;
		if(t==1) {
			int b, r; cin >> b >> r;
			b--;
			update(b, r);
		} else {
			int s, w; cin >> s >> w;
			s--;
			int lo = s, hi = n-1;
			int rres = s;
			while(lo <= hi) {
				int mid = (lo+hi)/2;
				int ret = query(s,mid);
				if(ret >= w) {
					rres = mid;
					lo = mid + 1;
				} else {
					hi = mid - 1;
				}
			}

			int lres = s;
			lo = 0, hi = s-1;
			while(lo <= hi) {
				int mid = (lo+hi)/2;
				int ret = query(mid, s);
				if(ret >= w) {
					lres = mid;
					hi = mid-1;
				} else {
					lo = mid + 1;
				}
			}

			cout << rres - lres + 1 << '\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