Submission #140553

#	Time	Username	Problem	Language	Result	Execution time	Memory
140553		luciocf	Bridges (APIO19_bridges)	C++14	0 / 100	451 ms	524292 KiB

bridges

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int maxn = 5e4+10;
const int maxm = 1e5+10;
const int inf = 1e9+10;

struct Edge
{
	int u, v, w;
} edge[maxn];

int n, m, q;
int tot;

int tree[4*maxn];

void build(int node, int l, int r)
{
	if (l == r)
	{
		tree[node] = edge[l].w;
		return;
	}

	int mid = (l+r)>>1;

	build(2*node, l, mid); build(2*node+1, mid+1, r);

	tree[node] = min(tree[2*node], tree[2*node+1]);
}

void upd(int node, int l, int r, int pos, int v)
{
	if (l == r)
	{
		tree[node] = v;
		return;
	}

	int mid = (l+r)>>1;

	if (pos <= mid) upd(2*node, l, mid, pos, v);
	else upd(2*node+1, mid+1, r, pos, v);

	tree[node] = min(tree[2*node], tree[2*node+1]);
}

int busca1(int node, int l, int r, int pos, int v)
{
	if (tree[node] >= v) return inf;

	if (l == r) return (l > pos ? l : inf);

	int mid = (l+r)>>1;

	if (mid <= pos || tree[2*node] >= v) return busca1(2*node+1, mid+1, r, pos, v);

	int p1 = busca1(2*node, l, mid, pos, v);
	if (p1 != inf) return p1;

	return busca1(2*node+1, mid+1, r, pos, v);
}

int busca2(int node, int l, int r, int pos, int v)
{
	if (tree[node] >= v) return inf;

	if (l == r) return (l < pos ? l : inf);

	int mid = (l+r)>>1;

	if (mid+1 >= pos || tree[2*node+1] >= v) return busca2(2*node, l, mid, pos, v);

	int p1 = busca2(2*node+1, mid+1, r, pos, v);
	if (p1 != inf) return p1;

	return busca2(2*node, l, mid, pos, v);
}

void solve_chain(void)
{
	build(1, 1, n-1);

	for (int i = 1; i <= q; i++)
	{
		int op;
		scanf("%d", &op);

		if (op == 1)
		{
			int ind, w;
			scanf("%d %d", &ind, &w);

			upd(1, 1, n-1, ind, w);
		}
		else
		{
			int u, w;
			scanf("%d %d", &u, &w);

			int r = busca1(1, 1, n-1, u-1, w);
			int l = busca2(1, 1, n-1, u, w);

			int ans = (r == inf ? n-u : r-u);

			ans += (l == inf ? u-1 : u-l-1);

			printf("%d\n", ans+1);
		}
	}
}

int main(void)
{
	scanf("%d %d", &n, &m);

	bool ok = 1;
	if (m != n-1) ok = 0;

	for (int i = 1; i <= m; i++)
	{
		int u, v, w;
		scanf("%d %d %d", &u, &v, &w);

		edge[i] = {u, v, w};

		if (v != i+1 || u != i) ok = 0;
	}

	scanf("%d", &q);
	
	solve_chain();
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:121:7: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
  bool ok = 1;
       ^~
bridges.cpp: In function 'void solve_chain()':
bridges.cpp:91:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &op);
   ~~~~~^~~~~~~~~~~
bridges.cpp:96:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d", &ind, &w);
    ~~~~~^~~~~~~~~~~~~~~~~~~
bridges.cpp:103:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d", &u, &w);
    ~~~~~^~~~~~~~~~~~~~~~~
bridges.cpp: In function 'int main()':
bridges.cpp:119:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~
bridges.cpp:127:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &u, &v, &w);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:134:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~

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