oj.uz

답안 #569169

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
569169 2022-05-26T21:14:25 Z aryan12 다리 (APIO19_bridges) C++17
16 / 100
 108 ms 4820 KB 
#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.0

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

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 69 ms 1896 KB Output is correct
2 Correct 70 ms 4616 KB Output is correct
3 Correct 77 ms 4688 KB Output is correct
4 Correct 72 ms 4700 KB Output is correct
5 Correct 70 ms 4700 KB Output is correct
6 Correct 76 ms 4708 KB Output is correct
7 Correct 77 ms 4668 KB Output is correct
8 Correct 80 ms 4684 KB Output is correct
9 Correct 27 ms 3472 KB Output is correct
10 Correct 59 ms 3700 KB Output is correct
11 Correct 60 ms 3644 KB Output is correct
12 Correct 93 ms 4820 KB Output is correct
13 Correct 59 ms 4580 KB Output is correct

Subtask #3
0 / 17.0

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

Subtask #4
0 / 14.0

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

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 69 ms 1896 KB Output is correct
2 Correct 70 ms 4616 KB Output is correct
3 Correct 77 ms 4688 KB Output is correct
4 Correct 72 ms 4700 KB Output is correct
5 Correct 70 ms 4700 KB Output is correct
6 Correct 76 ms 4708 KB Output is correct
7 Correct 77 ms 4668 KB Output is correct
8 Correct 80 ms 4684 KB Output is correct
9 Correct 27 ms 3472 KB Output is correct
10 Correct 59 ms 3700 KB Output is correct
11 Correct 60 ms 3644 KB Output is correct
12 Correct 93 ms 4820 KB Output is correct
13 Correct 59 ms 4580 KB Output is correct
14 Incorrect 62 ms 1996 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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