Submission #1174654

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174654		tkm_algorithms	Bridges (APIO19_bridges)	C++20	16 / 100	393 ms	3572 KiB

bridges

/**
*    In the name of Allah
*    We are nothing and you're everything
*    author: najmuddin
**/
#include <bits/stdc++.h>
using namespace std;
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
#define int ll
const char nl = '\n';
const int N = 5e4;
const int inf = 1e9;

struct segtree {
	vector<int> tree;
	int size;
	
	void init(int n) {
		size = 1;
		while (size < n)size <<= 1;
		tree.assign(2*size-1, inf);
	}
	
	void build(vector<int> &a, int x, int lx, int rx) {
		if (rx-lx == 1) {
			if (lx < sz(a))tree[x] = a[lx];
			return;
		}
		
		int mid = (lx + rx) >> 1;
		build(a, 2*x+1, lx, mid);
		build(a, 2*x+2, mid, rx);
		tree[x] = min(tree[2*x+1], tree[2*x+2]);
	}
	
	void build(vector<int> &a) {
		init(sz(a)+2);
		build(a, 0, 0, size);
	}
	
	void set(int i, int v, int x, int lx, int rx) {
		if (rx-lx == 1) {
			tree[x] = v;
			return;
		}
		
		int mid = (lx + rx) >> 1;
		if (i < mid)
			set(i, v, 2*x+1, lx, mid);
		else set(i, v, 2*x+2, mid, rx);
		tree[x] = min(tree[2*x+1], tree[2*x+2]);
	}
	
	void set(int i, int v) {
		set(i, v, 0, 0, size);
	}
	
	int get(int l, int r, int x, int lx, int rx) {
		if (lx >= l && rx <= r)return tree[x];
		if (rx <= l || r <= lx)return inf;
		int mid = (lx + rx) >> 1;
		int m1 = get(l, r, 2*x+1, lx, mid);
		int m2 = get(l, r, 2*x+2, mid, rx);
		return min(m1, m2);
	}
	
	int get(int l, int r) {
		return get(l, r, 0, 0, size);
	}
};

int32_t main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n, m, qq; cin >> n >> m;
	
	vector<int> arr(2, inf);
	for (int i = 0; i < m; ++i) {
		int a, b, w; cin >> a >> b >> w;
		arr.push_back(w);
	}
	
	segtree st;
	st.build(arr);
	
	cin >> qq;
	while (qq--) {
		int tp; cin >> tp;
		if (tp == 2) {
			int ans = 1;
			int x, w; cin >> x >> w;
			int l = 0, r = n-x+1;
			while (r-l > 1) {
				int mid = (l+r) >> 1;
				if (st.get(x+1, x+mid+1) >= w)l = mid;
				else r = mid;
			}
			
			ans += l;
			//cout << st.get(3, 4) << nl;
			
			l = 0, r = x;
			while (r-l>1) {
				int mid = (l + r) >> 1;
				if (st.get(x-mid+1, x+1) >= w)l = mid;
				else r = mid;
			}
			
			//cout << st.get(2, 6) << nl;
			
			cout << ans+l << nl;
		} else {
			int i, w; cin >> i >> w;
			st.set(i+1, w);
		}
	}
	return 0;
}

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