Submission #410676

#	Time	Username	Problem	Language	Result	Execution time	Memory
410676		dynam1c	Bridges (APIO19_bridges)	C++17	16 / 100	262 ms	3732 KiB

bridges

//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define endl "\n"
#define all(c) (c).begin(),(c).end()

// when you ponder, divide and conquer

struct RMQ {
	int n;
	vector<int> seg;
	RMQ(vector<int> arr) : n(arr.size()), seg(2*n) {
		for (int i = 0; i < n; i++)
			seg[i+n] = arr[i];
		for (int i = n-1; i > 0; i--)
			seg[i] = min(seg[i<<1], seg[i<<1|1]);
	}
	int query(int l, int r) {
		int acc = INT_MAX;
		for (l += n, r += n; l != r; l >>= 1, r >>= 1) {
			if (l&1) acc = min(acc, seg[l++]);
			if (r&1) acc = min(acc, seg[--r]);
		}
		return acc;
	}
	void update(int i, int x) {
		for (seg[i += n] = x; i > 1; i >>= 1)
			seg[i>>1] = min(seg[i], seg[i^1]);
	}
};

constexpr int L = 16;
signed main() {
	// freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n, m, q;
	cin >> n >> m;
	vector<int> ws(m);
	for (int i = 0; i < m; i++) {
		int x, y;
		cin >> x >> y >> ws[i];
	}
	cin >> q;
	RMQ rmq(ws);
	for (int qq = 0; qq < q; qq++) {
		int t, x, y;
		cin >> t >> x >> y;
		x--;
		if (t == 1) {
			rmq.update(x, y);
		} else {
			int l = x, r = x;
			for (int i = L-1; i >= 0; i--) {
				int d = 1<<i;
				if (r+d <= m and rmq.query(x, r+d) >= y)
					r += d;
				if (l-d >= 0 and rmq.query(l-d, x) >= y)
					l -= d;
			}
			cout << r-l+1 << endl;
		}
	}
}
/* --- PSolving ---
 * Simplifying (getting rid of variables, conditions, code logic, etc.)
 * Reframing
 * Solving a subtask (subgoal, aux. problem, removing a condition or fixing a parameter, etc.)
 * Inducing
 * Divide and conquer
 * Working backwards
 * Visual intuition
 * !! Reductions don't have to be specializations, they can be generalizations
 */

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