제출 #522294

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
522294		blue	I want to be the very best too! (NOI17_pokemonmaster)	C++17	16 / 100	5105 ms	305784 KiB

pokemonmaster

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

using vi = vector<int>;
using pii = pair<int, int>;
using vvi = vector<vi>;
using vpii = vector<pii>;

const int mx = 50'000;
const int lg = 16;

#define sz(x) int(x.size())

int R, C, Q;
int N;

vi L(mx), P(mx);

vi edge[mx];

void add_edge(int u, int v)
{
	edge[u].push_back(v);
	edge[v].push_back(u);
}









struct disjoint_set
{
	vi parent = vi(mx);
	vi subtree = vi(mx, 1);
	vpii peak = vpii(mx);

	disjoint_set()
	{
		for(int i = 0; i < mx; i++) 
		{
			parent[i] = i;
			peak[i] = {L[i], i};
		}

	}

	int root(int u)
	{
		if(parent[u] == u) return u;
		else return (parent[u] = root(parent[u]));
	}

	int getpeak(int u)
	{
		return peak[root(u)].second;
	}

	void join(int u, int v)
	{
		u = root(u);
		v = root(v);

		if(u == v) return;

		if(subtree[u] < subtree[v]) swap(u, v);

		parent[v] = u;
		subtree[u] += subtree[v];
		peak[u] = max(peak[u], peak[v]);
	}

	bool connected(int u, int v)
	{
		return root(u) == root(v);
	}
};








vi reach_children[mx];
vi reach_parent(mx);

vvi anc(mx, vi(1+lg));

vi subtree(mx, 1);
vi ord(1, -1);
vi ord_index(mx, 0);
vi depth(mx, 0);

int o_ct = 0;


void dfs(int u)
{
	ord.push_back(u);
	ord_index[u] = ++o_ct;

	for(int v : reach_children[u])
	{
		depth[v] = depth[u] + 1;
		dfs(v);
		subtree[u] += subtree[v];
	}
}

int ancestor(int u, int k)
{
	for(int e = 0; e <= lg; e++)
		if(k & (1 << e))
			u = anc[u][e];

	return u;
}

int lca(int u, int v)
{
	if(depth[u] > depth[v]) swap(u, v);
	v = ancestor(v, depth[v] - depth[u]);

	if(u == v) return u;

	for(int e = lg; e >= 0; e--)
	{
		if(anc[u][e] != anc[v][e])
		{
			u = anc[u][e];
			v = anc[v][e];
		}
	}

	return anc[u][0];
}















struct segtree
{
	int l;
	int r;

	int ct = 0;

	segtree* left = NULL;
	segtree* right = NULL;

	void insert(int I, int V)
	{
		ct += V;
		if(l != r)
		{
			int m = (l+r)/2;

			if(I <= m) 
			{
				if(left == NULL) left = new segtree{l, m, 0, NULL, NULL};
				left->insert(I, V);
			}
			else 
			{
				if(right == NULL) right = new segtree{m+1, r, 0, NULL, NULL};
				right->insert(I, V);
			}
		}
	}

	int count_leq(int I)
	{
		if(I >= r) return ct;
		else if(I < l) return 0;
		else
		{
			int lv = (left != NULL ? left->count_leq(I) : 0);
			int rv = (right != NULL ? right->count_leq(I) : 0);
			return lv + rv;
		}
	}
};




struct mst
{
	int l;
	int r;

	segtree v{0, mx, 0, NULL, NULL};

	mst* left = NULL;
	mst* right = NULL;

	mst()
	{
		;
	}

	mst(int L, int R)
	{
		l = L;
		r = R;
		if(l == r) return;
		int m = (l+r)/2;
		left = new mst(l, m);
		right = new mst(m+1, r);
	}

	void insert(int I, int J, int V)
	{
		v.insert(J, V);

		if(l != r)
		{
			if(I <= (l+r)/2) left->insert(I, J, V);
			else right->insert(I, J, V);
		}
	}

	int getcount(int L, int R, int X)
	{
		if(R < l || r < L) return 0;
		else if(L <= l && r <= R) return v.count_leq(X);
		else return left->getcount(L, R, X) + right->getcount(L, R, X);
	}
};















int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> R >> C >> Q;
	N = R * C;

	for(int i = 0; i < N; i++) cin >> L[i];

	for(int i = 0; i < N; i++) cin >> P[i];

	for(int r = 0; r < R-1; r++)
		for(int c = 0; c < C; c++)
			add_edge(C*r + c, C*(r+1) + c);

	for(int r = 0; r < R; r++)
		for(int c = 0; c < C-1; c++)
			add_edge(C*r + c, C*r + (c+1));












	vpii ord;
	for(int i = 0; i < N; i++)
		ord.push_back({L[i], i});

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

	disjoint_set DS;




	for(int i = 0; i < N; i++)
		reach_parent[i] = i;

	int rt;

	for(auto up: ord)
	{
		int u = up.second;

		rt = u;

		for(int v: edge[u])
		{
			if(L[v] >= L[u]) continue;

			if(DS.connected(u, v)) continue;

			int pu = DS.getpeak(u);
			int pv = DS.getpeak(v);

			reach_parent[pv] = pu;
			reach_children[pu].push_back(pv);

			DS.join(u, v);
		}
	}

	for(int i = 0; i < N; i++)
		anc[i][0] = reach_parent[i];

	for(int e = 1; e <= lg; e++)
		for(int i = 0; i < N; i++)
			anc[i][e] = anc[ anc[i][e-1] ][e-1];

	dfs(rt);



	vi prv_same(1+N, 0);//indexed by dfs order


	mst MST(1, N);

	{


		set<int> occ[1+mx];
		for(int p = 1; p <= mx; p++)
		{
			occ[p].insert(0);
		}

		for(int i = 0; i < N; i++)
			occ[P[i]].insert( ord_index[i] );

		for(int p = 1; p <= mx; p++)
		{
			int prvval = 0;

			for(int o : occ[p])
			{
				if(o == 0) continue;

				prv_same[o] = prvval;

				prvval = o;
			}
		}

		for(int id = 1; id <= N; id++)
			MST.insert(id, prv_same[id], +1);

	}


	



	for(int j = 0; j < Q; j++)
	{
		int T;
		cin >> T;

		if(T == 1)
		{
			int x, y, p;
			cin >> x >> y >> p;

			x--;
			y--;

			int z = C*y + x;

			P[z] = p;








			for(int id = 1; id <= N; id++)
				MST.insert(id, prv_same[id], -1);



			prv_same = vi(1+N, 0); //indexed by dfs order


			set<int> occ[1+mx];
			for(int p = 1; p <= mx; p++)
			{
				occ[p].insert(0);
			}

			for(int i = 0; i < N; i++)
				occ[P[i]].insert( ord_index[i] );

			for(int p = 1; p <= mx; p++)
			{
				int prvval = 0;

				for(int o : occ[p])
				{
					if(o == 0) continue;

					prv_same[o] = prvval;

					prvval = o;
				}
			}

			// MST = mst(1, N);

			for(int id = 1; id <= N; id++)
				MST.insert(id, prv_same[id], +1);


		}
		else
		{
			int x, y, l;
			cin >> x >> y >> l;

			x--;
			y--;

			set<int> res;

			int z = C*y + x;

			if(L[z] > l)
			{
				cout << 0 << '\n';
				continue;
			}

			for(int e = lg; e >= 0; e--)
				if(L[ anc[z][e] ] <= l)
					z = anc[z][e];

			int li = ord_index[z];
			int ri = ord_index[z] + subtree[z] - 1;

			cout << MST.getcount(li, ri, li-1) << '\n';
		}
	}
}

컴파일 시 표준 에러 (stderr) 메시지

pokemonmaster.cpp: In function 'int main()':
pokemonmaster.cpp:340:5: warning: 'rt' may be used uninitialized in this function [-Wmaybe-uninitialized]
  340 |  dfs(rt);
      |  ~~~^~~~

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