Submission #977473

#	Time	Username	Problem	Language	Result	Execution time	Memory
977473		dubabuba	Bridges (APIO19_bridges)	C++14	0 / 100	246 ms	4552 KiB

bridges

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

typedef pair<int, int> pii;
#define ff first
#define ss second
#define MP make_pair

const int mxn = 2e5 + 10;
int n, m, q, a[mxn], st[mxn * 4];

void build(int id, int tl, int tr) {
	if(tl == tr) {
		st[id] = a[tl];
		return;
	}
	int tm = (tl + tr) / 2;
	build(id * 2 + 1, tl, tm);
	build(id * 2 + 2, tm + 1, tr);
	st[id] = min(st[id * 2 + 1], st[id * 2 + 2]);
}

void upt(int id, int tl, int tr, int i, int w) {
	if(tl == tr) {
		st[id] = a[i] = w;
		return;
	}
	int tm = (tl + tr) / 2;
	if(i <= tm) upt(id * 2 + 1, tl, tm, i, w);
	else upt(id * 2 + 2, tm + 1, tr, i, w);
	st[id] = min(st[id * 2 + 1], st[id * 2 + 2]);
}

int query(int id, int tl, int tr, int i, int low) {
	if(st[id] > low) return tr - tl + 1;
	if(tl == tr) return 0;

	int tm = (tl + tr) / 2;
	if(i <= tm) {
		int LQ = query(id * 2 + 1, tl, tm, i, low);
		int RQ = 0;

		if(LQ == tm - tl + 1)
			RQ = query(id * 2 + 2, tm + 1, tr, tm + 1, low);
		return LQ + RQ;
	}

	int LQ = 0;
	int RQ = query(id * 2 + 2, tm + 1, tr, i, low);
	if(RQ == tr - tm)
		LQ = query(id * 2 + 1, tl, tm, tm, low);
	return LQ + RQ;
}

int main() {
	cin >> n >> m;
	for(int i = 0; i < m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		a[i] = w;
	}

	build(0, 0, m - 1);

	cin >> q;
	for(int i = 0; i < q; i++) {
		int t, s, w;
		cin >> t >> s >> w;
		if(t == 1) upt(0, 0, m - 1, s - 1, w);
		else {
			pii L = ((s < 2) ? MP(-1, -1) : MP(s - 2, a[s - 2]));
			pii R = ((s < n) ? MP(s - 1, a[s - 1]) : MP(-1, -1));
			pii P = max(L, R);

			cout << query(0, 0, m - 1, P.ss, w) << endl;
		}
	}
	return 0;
}

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