Submission #569169

#	Time	Username	Problem	Language	Result	Execution time	Memory
569169		aryan12	Bridges (APIO19_bridges)	C++17	16 / 100	108 ms	4820 KiB

bridges

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

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

const int N = 5e4 + 5, INF = 1e15;
// vector<array<int, 2> > g[N];
// vector<array<int, 3> > edges(N * 2);
// int par[N], siz[N];
int n;

vector<int> seg(N * 4, INF);

// int dfs(int node, int wt)
// {
// 	vis[node] = true;
// 	int ans = 1;
// 	for(auto [to, idx]: g[node])
// 	{
// 		int cur_wt = edges[idx][2];
// 		if(cur_wt >= wt && !vis[to])
// 		{
// 			ans += dfs(to, wt);
// 		}
// 	}
// 	return ans;
// }

// int Find(int x)
// {
// 	if(x == par[x]) return x;
// 	return par[x] = Find(par[x]);
// }

// void Unite(int a, int b)
// {
// 	a = Find(a), b = Find(b);
// 	if(a == b) return;
// 	siz[a] += siz[b];
// 	par[b] = a;
// }

// bool cmp(array<int, 4> a, array<int, 4> b)
// {
// 	if(a[3] == b[3]) return a[0] < b[0];
// 	return a[3] > b[3];
// }

void Update(int l, int r, int pos, int qpos, int qval)
{
	if(l == r)
	{
		seg[pos] = qval;
		return;
	}
	int mid = (l + r) >> 1;
	if(qpos <= mid) Update(l, mid, pos * 2, qpos, qval);
	else Update(mid + 1, r, pos * 2 + 1, qpos, qval);
	seg[pos] = min(seg[pos * 2], seg[pos * 2 + 1]);
}

int QueryLeft(int l, int r, int pos, int ql, int qr, int qval)
{
	// cout << "Query Left: " << l << ", " << r << ", " << pos << ", " << ql << ", " << qr << ", " << qval << "\n";
	if(ql > r || l > qr) return n;
	if(ql <= l && r <= qr && seg[pos] >= qval) return n;
	if(l == r) return l;
	int mid = (l + r) >> 1;
	int ans1 = QueryLeft(l, mid, pos * 2, ql, qr, qval);
	if(ans1 == n) return QueryLeft(mid + 1, r, pos * 2 + 1, ql, qr, qval);
	return ans1;
}

int QueryRight(int l, int r, int pos, int ql, int qr, int qval)
{
	// cout << "Query Right: " << l << ", " << r << ", " << pos << ", " << ql << ", " << qr << ", " << qval << "\n";
	if(ql > r || l > qr) return 0;
	if(ql <= l && r <= qr && seg[pos] >= qval) return 0;
	if(l == r) return l;
	int mid = (l + r) >> 1;
	int ans1 = QueryRight(mid + 1, r, pos * 2 + 1, ql, qr, qval);
	if(ans1 == 0) return QueryRight(l, mid, pos * 2, ql, qr, qval);
	return ans1;
}

void Solve() 
{
	int m;
	cin >> n >> m;
	// for(int i = 0; i <= n; i++)
	// {
	// 	par[i] = i;
	// 	siz[i] = 1;
	// }
	for(int i = 1; i <= m; i++)
	{
		int u, v, w;
		cin >> u >> v >> w;
		// g[u].push_back({v, i});
		// g[v].push_back({u, i});
		// cout << "at position: " << u << ", value: " << w << "\n";
		Update(1, n - 1, 1, u, w);
	}
	int q;
	cin >> q;
	for(int i = 1; i <= q; i++)
	{
		int command;
		cin >> command;
		if(command == 1)
		{
			int pos, val;
			cin >> pos >> val;
			Update(1, n - 1, 1, pos, val);
		}
		else
		{
			int pos, val;
			cin >> pos >> val;
			int ans1 = QueryRight(1, n - 1, 1, 1, pos - 1, val), ans2 = QueryLeft(1, n - 1, 1, pos, n - 1, val);
			ans1++;
			// cout << "ans1 = " << ans1 << ", ans2 = " << ans2 << "\n";
			cout << ans2 - ans1 + 1 << "\n";
		}
	}
}

int32_t main() 
{
	auto begin = std::chrono::high_resolution_clock::now();
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	// cin >> t;
	for(int i = 1; i <= t; i++) 
	{
		//cout << "Case #" << i << ": ";
		Solve();
	}
	auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
	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