Submission #382981

#	Time	Username	Problem	Language	Result	Execution time	Memory
382981		milleniumEeee	Bridges (APIO19_bridges)	C++17	16 / 100	1138 ms	7988 KiB

bridges

#include <bits/stdc++.h>
#define fastInp ios_base::sync_with_stdio(0); cin.tie(0);
#define pii pair<int, int>
#define fr first
#define sc second
#define mk make_pair
#define pb push_back
#define szof(s) (int)s.size()
#define all(s) s.begin(), s.end()
using namespace std;

const int MAXN = (int)1e5 + 5;
const int INF = (int)2e9 + 7;
const int L = 20;

vector <pii> g[MAXN];
int edge[MAXN];
int n, m, q;

struct Query {
	int type, x, y;
	Query (int type_, int x_, int y_) {
		type = type_;
		x = x_;
		y = y_;
	}
	Query () {
		
	}
};

Query qr[MAXN];

int tree[MAXN * 4];

void upd(int pos, int val, int v = 1, int tl = 1, int tr = MAXN) {
	if (tl == tr) {
		tree[v] = val;
		return;
	}
	int mid = (tl + tr) >> 1;
	if (pos <= mid) {
		upd(pos, val, v + v, tl, mid);
	} else {
		upd(pos, val, v + v + 1, mid + 1, tr);
	}
	tree[v] = min(tree[v + v], tree[v + v + 1]);
}

int get(int l, int r, int v = 1, int tl = 1, int tr = MAXN) {
	if (l > tr || tl > r) {
		return INF;
	}
	if (l <= tl && tr <= r) {
		return tree[v];
	}
	int mid = (tl + tr) >> 1;
	return min(get(l, r, v + v, tl, mid), get(l, r, v + v + 1, mid + 1, tr));
}

signed main() {
	fastInp;
	fill(tree, tree + MAXN * 4, INF);
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int u, v, val;
		cin >> u >> v >> val;
		edge[i] = val;
		g[u].pb({v, i});
		g[v].pb({u, i});
	}
	for (int i = 1; i <= m; i++) {
		upd(i, edge[i]);
	}
	cin >> q;
	for (int i = 1; i <= q; i++) {
		int type;
		cin >> type;
		if (type == 1) {
			int pos, new_val;
			cin >> pos >> new_val;
			edge[pos] = new_val;
			upd(pos, new_val);
		}
		else {
			int vertex, x;
			cin >> vertex >> x;
			int l, r;
			l = r = vertex;
			if (vertex < n && edge[vertex] >= x) {
				int lft = vertex, rgt = m + 1;
				while (rgt - lft > 1) {
					int mid = (lft + rgt) >> 1;
					if (get(vertex, mid) >= x) {
						lft = mid;
					} else {
						rgt = mid;
					}
				}
				r = lft + 1;
			}
			if (vertex > 1 && edge[vertex - 1] >= x) {
				int lft = 0, rgt = vertex - 1;
				while (rgt - lft > 1) {
					int mid = (lft + rgt) >> 1;
					if (get(mid, vertex - 1) >= x) {
						rgt = mid;
					} else {
						lft = mid;
					}
				}
				l = rgt;
			}
			cout << r - l + 1 << endl;
		}
	}
}

/*
2 1
1 2 50
4
1 1 32
2 1 40
2 1 1
2 2 38

*/

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