Submission #700844

#	Time	Username	Problem	Language	Result	Execution time	Memory
700844		anonimy	I want to be the very best too! (NOI17_pokemonmaster)	C++14	0 / 100	196 ms	17352 KiB

pokemonmaster

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<ll, pll> ppll;

vector<ll> head, group, vals, tin, tout;
vector<vector<ll>> tree, st;
ll t = -1, logsz;

struct seg
{
	vector<ll> a;
	ll sz;

	seg(ll n)
	{
		for (sz = 1; sz < n; sz <<= 1);
		a.resize(sz * 2, 0);
	}

	void update(ll ind, ll x)
	{
		ind += sz;
		a[ind] = x;
		for (ind >>= 1; ind; ind >>= 1)
			a[ind] = a[ind * 2] + a[ind * 2 + 1];
	}

	ll q(ll l, ll r)
	{
		l += sz, r += sz;

		ll ans = 0;
		while (l<=r)
		{
			if (l % 2 == 1) ans += a[l++];
			if (r % 2 == 0) ans += a[r--];
			l >>= 1;
			r >>= 1;
		}

		return ans;
	}
};

ll gethead(ll v)
{
	if (head[v] == v)
		return v;
	return head[v] = gethead(head[v]);
}

void unit(ll v, ll u)
{
	u = gethead(u);

	if (head[u] != v)
		head[u] = v, group[v] += group[u], st[0][u] = v;
}

ll getlog(ll n)
{
	ll ans = 0;
	while (n)
	{
		n >>= 1;
		ans++;
	}

	return ans;
}

ll getpar(ll ind, ll maxl)
{
	for (ll i = logsz - 1; i >= 0; i--)
		if (vals[st[i][ind]] <= maxl)
			ind = st[i][ind];

	if (vals[st[0][ind]] <= maxl)
		ind = st[0][ind];

	return ind;
}

void dfs(ll v, ll p)
{
	tin[v] = ++t;
	for (ll i = 0; i < tree[v].size(); i++)
	{
		ll u = tree[v][i];

		if (u == p) continue;

		dfs(u, v);
	}
	tout[v] = t;
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	ll r, c, q;
	cin >> r >> c >> q;

	vector<vector<ll>> l(r, vector<ll>(c)), p(r, vector<ll>(c));
	for (ll i = 0; i < r; i++)
		for (ll j = 0; j < c; j++)
			cin >> l[i][j];

	for (ll i = 0; i < r; i++)
		for (ll j = 0; j < c; j++)
			cin >> p[i][j];

	vector<ppll> order;
	for (ll i = 0; i < r; i++)
		for (ll j = 0; j < c; j++)
			order.push_back({ l[i][j], {i, j} });

	sort(order.begin(), order.end());

	ll sz = r * c;
	group.resize(sz, 1);
	head.resize(sz);
	for (ll i = 0; i < sz; i++)
		head[i] = i;

	logsz = getlog(sz) + 2;
	st.resize(logsz, vector<ll>(sz));
	for (ll i = 0; i < sz; i++)
		st[0][i] = i;
	for (ll i = 0; i < sz; i++)
	{
		ll x = order[i].second.first, y = order[i].second.second;
		ll ind = x * c + y;

		if (x && l[x][y] > l[x - 1][y])
			unit(ind, ind - c);
		if (y && l[x][y] > l[x][y - 1])
			unit(ind, ind - 1);
		if (x<r - 1 && l[x][y] > l[x + 1][y])
			unit(ind, ind + c);
		if (y<c - 1 && l[x][y] > l[x][y + 1])
			unit(ind, ind + 1);
	}

	for (ll i = 1; i < logsz; i++)
		for (ll j = 0; j < sz; j++)
			st[i][j] = st[i - 1][st[i - 1][j]];

	vals.resize(r * c);
	for (ll i = 0; i < r; i++)
		for (ll j = 0; j < c; j++)
			vals[i * c + j] = l[i][j];

	ll root = order.back().second.first * c + order.back().second.second;
	tree.resize(r * c);
	for (ll i = 0; i < r * c; i++)
	{
		tree[i].push_back(st[0][i]);
		tree[st[0][i]].push_back(i);
	}

	tin.resize(sz);
	tout.resize(sz);
	dfs(root, root);

	seg s(sz);
	for (ll i = 0; i < r; i++)
		for (ll j = 0; j < c; j++)
			s.update(tin[i * c + j], p[i][j]);

	while (q--)
	{
		ll type;
		cin >> type;

		if (type == 1)
		{
			ll x, y, newp;
			cin >> x >> y >> newp;
			x--, y--;
			swap(x, y);

			ll ind = x * c + y;
			s.update(tin[ind], newp);
		}
		else
		{
			ll x, y, newl;
			cin >> x >> y >> newl;
			x--, y--;
			swap(x, y);

			if (l[x][y] > newl)
			{
				cout << 0 << "\n";
				continue;
			}

			ll ind = x * c + y;
			ind = getpar(ind, newl);

			ll ans = s.q(tin[ind], tout[ind]);
			if (ans != group[ind] && ans!=0)
				cout << 2 << "\n";
			else
				cout << 1 << "\n";
		}
	}
}

Compilation message (stderr)

pokemonmaster.cpp: In function 'void dfs(ll, ll)':
pokemonmaster.cpp:93:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |  for (ll i = 0; i < tree[v].size(); i++)
      |                 ~~^~~~~~~~~~~~~~~~

• Subtask 1: 0 / 11
• Subtask 2: 0 / 16
• Subtask 3: 0 / 20
• Subtask 4: 0 / 24
• Subtask 5: 0 / 29