Submission #293898

#	Time	Username	Problem	Language	Result	Execution time	Memory
293898		Berted	I want to be the very best too! (NOI17_pokemonmaster)	C++14	47 / 100	5075 ms	88784 KiB

pokemonmaster

#include <iostream>
#include <vector>
#include <algorithm>
#include <assert.h>
#include <set>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define vi vector<int>
#define pii pair<int, int>
#define fst first
#define snd second
#define pub push_back
using namespace std;
using namespace __gnu_pbds;

typedef tree<
pii,
null_type,
less<pii>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;

int ask = 0;

const int LG = 17, SZ = (1 << 17) + 5, INF = 1e9;

int r, c, q;
pii A[100001];
int P[100001];

vi adj[100001], ord; int treeSZ = 0;
int T[100001], L[100001], R[100001], sps[100001][LG], h[100001], rev[50001];
int par[100001], cur[100001];

ordered_set seg[SZ];
set<int> s[50001];

void del(int idx, int L, int R, int x, int v)
{
	if (L < R)
	{
		int M = L + R >> 1;
		if (x <= M) del(2 * idx, L, M, x, v);
		else del(2 * idx + 1, M + 1, R, x, v);
	}
	seg[idx].erase(seg[idx].lower_bound({v, 0}));
}

void ins(int idx, int L, int R, int x, int v)
{
	if (L < R)
	{
		int M = L + R >> 1;
		if (x <= M) ins(2 * idx, L, M, x, v);
		else ins(2 * idx + 1, M + 1, R, x, v);
	}
	seg[idx].insert({v, ask++});
}

int qry(int idx, int L, int R, int l, int r, int v)
{
	l = max(L, l); r = min(R, r);
	if (l <= r)
	{
		if (L == l && R == r) 
		{
			return seg[idx].order_of_key({v, 0});
		}
		else
		{
			int M = L + R >> 1;
			return qry(2 * idx, L, M, l, r, v) + qry(2 * idx + 1, M + 1, R, l, r, v);
		}
	}
	return 0;
}

int fn(int x) {return par[x] = (par[x] != x) ? fn(par[x]) : x;}
void jn(int a, int b, int t)
{
	a = fn(a), b = fn(b);
	if (a != b)
	{
		par[b] = a;
		adj[treeSZ].push_back(cur[a]);
		adj[treeSZ].push_back(cur[b]);
		T[treeSZ] = t;
		cur[a] = treeSZ++;
	}
}

void DFS(int u, int p)
{
	h[u] = (p == -1) ? 0 : (h[p] + 1); sps[u][0] = p;
	for (int i = 1; i < LG; i++)
	{
		if (sps[u][i - 1] != -1) {sps[u][i] = sps[sps[u][i - 1]][i - 1];}
		else {sps[u][i] = -1;}
	}
	bool isLeaf = 1; L[u] = 2 * r * c; R[u] = - 2 * r * c;
	for (auto v : adj[u])
	{
		if (v != p)
		{
			DFS(v, u);
			L[u] = min(L[u], L[v]);
			R[u] = max(R[u], R[v]);
			isLeaf = 0;
		}
	}
	if (isLeaf)
	{
		L[u] = R[u] = ord.size();
		ord.push_back(u);
	}
}

int findRep(int u, int t)
{
	if (T[u] > t) {return -1;}
	for (int i = LG - 1; i >= 0; i--)
	{
		if (sps[u][i] != -1 && T[sps[u][i]] <= t) {u = sps[u][i];}
	}
	return u;
}

int main()
{
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> r >> c >> q;
	for (int i = 0; i < r * c; i++) {cin >> A[i].fst; A[i].snd = i; par[i] = -1;}
	for (int i = 0; i < r * c; i++) {cin >> P[i];}
	treeSZ = r * c;
	sort(A, A + r * c);
	for (int i = 0; i < r * c; i++)
	{
		par[A[i].snd] = A[i].snd; cur[A[i].snd] = A[i].snd; T[A[i].snd] = A[i].fst;
		int y = A[i].snd / c, x = A[i].snd % c;
		if (y + 1 < r && par[(y + 1) * c + x] != -1) {jn((y + 1) * c + x, A[i].snd, A[i].fst);}
		if (x + 1 < c && par[y * c + x + 1] != -1) {jn(y * c + x + 1, A[i].snd, A[i].fst);}
		if (x && par[y * c + x - 1] != -1) {jn(y * c + x - 1, A[i].snd, A[i].fst);}
		if (y && par[(y - 1) * c + x] != -1) {jn((y - 1) * c + x, A[i].snd, A[i].fst);}
	}
	DFS(treeSZ - 1, -1);
	for (int i = 0; i < r * c; i++) 
	{
		rev[ord[i]] = i;

		if (s[P[ord[i]]].size() == 0) {ins(1, 0, r * c - 1, i, -INF);}
		else {ins(1, 0, r * c - 1, i, *prev(s[P[ord[i]]].end()));}

		s[P[ord[i]]].insert(i);
	}
	for (int i = 0; i < q; i++)
	{
		int qq, x, y, t; cin >> qq >> x >> y >> t; x--; y--;
		if (qq == 1) 
		{
			int vv = P[y * c + x];
			set<int>::iterator it = s[vv].lower_bound(rev[y * c + x]);
			if (it == s[vv].begin()) {del(1, 0, r * c - 1, rev[y * c + x], -INF);}
			else {del(1, 0, r * c - 1, rev[y * c + x], *prev(it));}
			if (next(it) != s[vv].end()) {del(1, 0, r * c - 1, *next(it), rev[y * c + x]);}
			assert(it != s[vv].end() && *it == rev[y * c + x]);
			
			it = s[vv].erase(it);
			if (it != s[vv].end())
			{
				if (it == s[vv].begin()) {ins(1, 0, r * c - 1, *it, -INF);}
				else {ins(1, 0, r * c - 1, *it, *prev(it));}
			}

			it = s[t].upper_bound(rev[y * c + x]);
			if (it != s[t].end())
			{
				if (it == s[t].begin()) {del(1, 0, r * c - 1, *it, -INF);}
				else {del(1, 0, r * c - 1, *it, *prev(it));}
			}

			it = s[t].insert(it, rev[y * c + x]);
			if (it == s[t].begin()) {ins(1, 0, r * c - 1, rev[y * c + x], -INF);}
			else {ins(1, 0, r * c - 1, rev[y * c + x], *prev(it));}
			if (next(it) != s[t].end()) {ins(1, 0, r * c - 1, *next(it), rev[y * c + x]);}
			
			P[y * c + x] = t;
		}
		else
		{
			int u = findRep(y * c + x, t);
			if (u == -1) {cout << "0\n";}
			else {cout << qry(1, 0, r * c - 1, L[u], R[u], L[u]) << "\n";}
		}
	}
	return 0;
}

Compilation message (stderr)

pokemonmaster.cpp: In function 'void del(int, int, int, int, int)':
pokemonmaster.cpp:43:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |   int M = L + R >> 1;
      |           ~~^~~
pokemonmaster.cpp: In function 'void ins(int, int, int, int, int)':
pokemonmaster.cpp:54:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |   int M = L + R >> 1;
      |           ~~^~~
pokemonmaster.cpp: In function 'int qry(int, int, int, int, int, int)':
pokemonmaster.cpp:72:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   72 |    int M = L + R >> 1;
      |            ~~^~~

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