Submission #567829

#	Time	Username	Problem	Language	Result	Execution time	Memory
567829		8e7	Bridges (APIO19_bridges)	C++17	16 / 100	636 ms	3772 KiB

bridges

//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T,class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 50005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
const int inf = 1<<30;
const int bs = 200;

struct segtree{
	int seg[4 * maxn];
	void modify(int cur, int l, int r, int ind, int x) {
		if (r <= l) return;
		if (r - l == 1) {
			seg[cur] = x;
			return;
		}
		int m = (l + r) / 2;
		if (ind < m) modify(cur*2, l, m, ind, x);
		else modify(cur*2+1, m, r, ind, x);
		seg[cur] = min(seg[cur*2], seg[cur*2+1]);
	}
	int query(int cur, int l, int r, int ql, int qr) {
		if (r <= l || ql >= r || qr <= l) return inf;
		if (ql <= l && qr >= r) return seg[cur];
		int m = (l + r) / 2;
		return min(query(cur*2, l, m, ql, qr), query(cur*2+1, m, r, ql, qr));
	}
} tr;

int main() {
	io
	int n, m;
	cin >> n >> m;
	for (int i = 0;i < m;i++) {
		int u, v, w;
		cin >> u >> v >> w;
		tr.modify(1, 0, n-1, i, w);
	}
	
	int q;
	cin >> q;
	while (q--) {
		int type; cin >> type;
		if (type == 1) {
			int bi, ri;
			cin >> bi >> ri;
			bi--;
			tr.modify(1, 0, n-1, bi, ri);
		} else {
			int s, w;
			cin >> s >> w;
			s--;
			int lef = s, rig = s;
			int low = -1, up = s;
			while (low < up - 1) {
				int mid = (low + up) / 2;
				if (tr.query(1, 0, n-1, mid, s) >= w) up = mid;
				else low = mid;
			}
			lef = up;
			low = s, up = n;
			while (low < up - 1) {
				int mid = (low + up) / 2;
				if (tr.query(1, 0, n-1, s, mid) >= w) low = mid;
				else up = mid;
			}
			rig = low;
			cout << rig - lef + 1 << "\n";
		}
	}
}
/*
7 6
1 2 4
1 3 5
2 4 2
2 5 1
3 6 7
3 7 3
5
2 3 3
1 4 3
2 3 5
2 2 2
2 1 6
*/

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