Submission #1174703

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174703		Muhammet	Bridges (APIO19_bridges)	C++17	16 / 100	495 ms	4660 KiB

bridges

#include "bits/stdc++.h"

using namespace std;

const int N = 1e5 + 5;

int st[N * 4];

vector <int> v[N], vis;

int upd(int nd, int l, int r, int x, int vl) {
	if(l > x or r < x) return st[nd];
	if(l == r) return st[nd] = vl;
	int md = (l + r) / 2;
	return st[nd] = min(upd(nd*2, l, md, x, vl), upd(nd*2+1, md+1, r, x, vl));
}

int fnd(int nd, int l, int r, int x, int y) {
	if(l > y or r < x) return 1e9;
	if(l >= x and r <= y) return st[nd];
	int md = (l + r) / 2;
	return min(fnd(nd*2, l, md, x, y), fnd(nd*2+1, md+1, r, x, y));
}

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

	int n, m;
	cin >> n >> m;
	vector <int> u1(m+1), u2(m+1), d(m+1);
	for(int i = 1; i <= m; i++) {
		cin >> u1[i] >> u2[i] >> d[i];
		upd(1, 1, n, i, d[i]);
	}
	int q;
	cin >> q;
	for(int i = 1; i <= q; i++) {
		int t;
		cin >> t;
		if(t == 1) {
			int b, r;
			cin >> b >> r;
			upd(1, 1, n, b, r);
		}
		else {
			int s, w;
			cin >> s >> w;
			int l = s, r = n-1, k = s;
			while(l <= r) {
				int md = (l + r) / 2;
				if(fnd(1, 1, n, s, md) >= w) {
					l = md+1;
					k = md+1;
				}
				else {
					r = md-1;
				}
			}
			l = 1, r = s-1;
			int k1 = s;
			while(l <= r) {
				int md = (l + r) / 2;
				if(fnd(1, 1, n, md, s-1) >= w) {
					r = md-1;
					k1 = md;
				}
				else {
					l = md+1;
				}
			}
			cout << (k - k1 + 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