Submission #700884

#	Time	Username	Problem	Language	Result	Execution time	Memory
700884		anonimy	I want to be the very best too! (NOI17_pokemonmaster)	C++14	0 / 100	173 ms	22236 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;

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;
	}
};

vector<ll> par, sz, root;
vector<ll> vals;
vector<ll> tin, tout, sons;
vector<vector<ll>> st, tree;
ll logn, t = -1;

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

ll getpar(ll v)
{
	if (par[v] == v)
		return v;
	return par[v] = getpar(par[v]);
}

void unit(ll v, ll u, ll r)
{
	u = getpar(u);

	if (v == u)
	{
		root[v] = r;
		return;
	}

	if (sz[u] > sz[v]) swap(u, v);
	par[u] = v;
	sz[v] += sz[u];
	root[v] = r;
}

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

ll getmaxl(ll ind, ll maxl)
{
	for (ll i = logn - 1; i >= 0; i--)
		if (vals[st[i][ind]] <= maxl)
			ind = st[i][ind];
	
	return ind;
}

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

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

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

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

	ll n = r * c;
	vector<ppll> order(n);
	for(ll i=0;i<r;i++)
		for (ll j = 0; j < c; j++)
		{
			ll ind = i * c + j;
			order[ind] = { level[i][j], {i, j} };
		}
	sort(order.begin(), order.end());

	sz.resize(n, 1);
	par.resize(n);
	root.resize(n);
	for (ll i = 0; i < n; i++)
		par[i] = root[i] = i;

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

		if (x && l > level[x - 1][y])
		{
			ll nei = (x - 1) * c + y;
			nei = getpar(nei);
			nei = root[nei];
			st[0][nei] = ind;
			unit(ind, nei, ind);
		}

		if (y && l > level[x][y - 1])
		{
			ll nei = x * c + y - 1;
			nei = getpar(nei);
			nei = root[nei];
			st[0][nei] = ind;
			unit(ind, nei, ind);
		}

		if (x < r - 1 && l > level[x + 1][y])
		{
			ll nei = (x + 1) * c + y;
			nei = getpar(nei);
			nei = root[nei];
			st[0][nei] = ind;
			unit(ind, nei, ind);
		}

		if (y<c - 1 && l > level[x][y + 1])
		{
			ll nei = x * c + y + 1;
			nei = getpar(nei);
			nei = root[nei];
			st[0][nei] = ind;
			unit(ind, nei, ind);
		}
	}

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

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

	tree.resize(n);
	for (ll i = 0; i < n; i++)
		if (st[0][i] != i)
			tree[st[0][i]].push_back(i);
	
	ll bigroot = order.back().second.first * c + order.back().second.second;
	tin.resize(n);
	tout.resize(n);
	sons.resize(n, 1);
	dfs(bigroot);

	seg s(n);
	for(ll i=0;i<r;i++)
		for (ll j = 0; j < c; j++)
			s.update(tin[i * c + j], pokemon[i][j] - 1);
	
	while (q--)
	{
		ll type;
		cin >> type;

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

			s.update(tin[x * c + y], p);
		}
		else
		{
			ll x, y, l;
			cin >> x >> y >> l;
			x--, y--;
			swap(x, y);

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

			ll ind = x * c + y;
			ind = getmaxl(ind, l);
			ll sum = s.q(tin[ind], tout[ind]);
			if (sum == sons[ind] || sum == 0)
				cout << 1 << "\n";
			else
				cout << 2 << "\n";
		}
	}
}

Compilation message (stderr)

pokemonmaster.cpp: In function 'void dfs(ll)':
pokemonmaster.cpp:87: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]
   87 |  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