oj.uz

답안 #382981

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
382981 2021-03-28T16:22:39 Z milleniumEeee 다리 (APIO19_bridges) C++17
16 / 100
 1138 ms 7988 KB 
#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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 4204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 409 ms 6212 KB Output is correct
2 Correct 414 ms 6124 KB Output is correct
3 Correct 400 ms 6184 KB Output is correct
4 Correct 399 ms 6252 KB Output is correct
5 Correct 402 ms 6252 KB Output is correct
6 Correct 670 ms 6360 KB Output is correct
7 Correct 666 ms 6508 KB Output is correct
8 Correct 664 ms 6252 KB Output is correct
9 Correct 243 ms 4460 KB Output is correct
10 Correct 518 ms 6380 KB Output is correct
11 Correct 490 ms 6404 KB Output is correct
12 Correct 1138 ms 6508 KB Output is correct
13 Correct 216 ms 6252 KB Output is correct

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 379 ms 5740 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 830 ms 7988 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 409 ms 6212 KB Output is correct
2 Correct 414 ms 6124 KB Output is correct
3 Correct 400 ms 6184 KB Output is correct
4 Correct 399 ms 6252 KB Output is correct
5 Correct 402 ms 6252 KB Output is correct
6 Correct 670 ms 6360 KB Output is correct
7 Correct 666 ms 6508 KB Output is correct
8 Correct 664 ms 6252 KB Output is correct
9 Correct 243 ms 4460 KB Output is correct
10 Correct 518 ms 6380 KB Output is correct
11 Correct 490 ms 6404 KB Output is correct
12 Correct 1138 ms 6508 KB Output is correct
13 Correct 216 ms 6252 KB Output is correct
14 Incorrect 379 ms 5740 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 4204 KB Output isn't correct
2 Halted 0 ms 0 KB -