Submission #1173937

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173937		stdfloat	다리 (APIO19_bridges)	C++20	16 / 100	471 ms	1644 KiB

bridges

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

vector<int> st;

int upd(int nd, int l, int r, int x, int vl) {
	if (r < x || x < l) return st[nd];

	if (l == r) return st[nd] = vl;

	int ch = (nd << 1) + 1, md = (l + r) >> 1;
	return st[nd] = min(upd(ch, l, md, x, vl), upd(ch + 1, md + 1, r, x, vl));
}

int fnd(int nd, int l, int r, int x, int y) {
	if (r < x || y < l) return INT_MAX;

	if (x <= l && r <= y) return st[nd];

	int ch = (nd << 1) + 1, md = (l + r) >> 1;
	return min(fnd(ch, l, md, x, y), fnd(ch + 1, md + 1, r, x, y));
}

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);

	int n, m;
	cin >> n >> m;

	assert(m == n - 1);

	st.assign(m << 2, 0);
	for (int i = 0; i < m; i++) {
		int u, v, d;
		cin >> u >> v >> d; u--; v--;

		assert(u == i && v == i + 1);	
	
		upd(0, 0, m - 1, i, d);
	}

	int q;
	cin >> q;
	while (q--) {
		int t;
		cin >> t;
	
		if (t == 1) {
			int b, r;
			cin >> b >> r; b--;

			upd(0, 0, m - 1, b, r);
		}
		else {
			int s, w;
			cin >> s >> w; s--;

			int l = 0, r = s - 1;
			while (l <= r) {
				int md = (l + r) >> 1;

				if (fnd(0, 0, m - 1, md, s - 1) < w) l = md + 1;
				else r = md - 1;
			}

			int rem = l;

			l = s; r = m - 1;
			while (l <= r) {
				int md = (l + r) >> 1;

				if (w <= fnd(0, 0, m - 1, s, md)) l = md + 1;
				else r = md - 1;
			}

			cout << l - rem + 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