Submission #522548

#	Time	Username	Problem	Language	Result	Execution time	Memory
522548		blue	I want to be the very best too! (NOI17_pokemonmaster)	C++17	100 / 100	3479 ms	319848 KiB

pokemonmaster

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <cassert>
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())
#define dbg if(debugging)cerr
 
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);
}
 
 
 
 
bool debugging = 1;
 
 
 
 
 
 
 
 
 
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);
 
	// 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;
		}
	}
};
 
segtree* attach(segtree* st, int I, int V, int lv, int rv)
{
	segtree* ln = new segtree{I, I, V, NULL, NULL};
 
	segtree* rn = st;
 
	if(ln->l > rn->l) swap(ln, rn);
 
	assert(ln->r < rn->l);
 
	while(1)
	{
		if((lv+rv)/2 >= rn->r)
			rv = (lv+rv)/2;
		else if((lv+rv)/2+1 <= ln->l)
			lv = (lv+rv)/2+1;
		else break;
	}
 
	return new segtree{lv, rv, ln->ct + rn->ct, ln, rn};
}
 
 
void segtree::insert(int I, int V)
{
	ct += V;
	if(l != r)
	{
		int m = (l+r)/2;
 
		if(I <= m) 
		{
			if(left == NULL) left = new segtree{I, I, V, NULL, NULL};
			else if(left->l <= I && I <= left->r) left->insert(I, V);
			else left = attach(left, I, V, l, r);
		}
		else 
		{
			if(right == NULL) right = new segtree{I, I, V, NULL, NULL};
			else if(right->l <= I && I <= right->r) right->insert(I, V);
			else right = attach(right, I, V, l, r);
		}
	}
}
 
 
 
 
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)
	{
		// if(l == 1 && r == N) cerr << I << ' ' << J << " : " << V << '\n';
 
		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);
 
	// for(int i = 0; i < N; i++) cerr << ord_index[i] << ' ';
	// 	cerr << "\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;
 
			// cerr << "prv same " << o << " = " << prvval << '\n';
 
			prvval = o;
		}
	}
 
	for(int id = 1; id <= N; id++)
		MST.insert(id, prv_same[id], +1);
 
 
	
	// for(int i = 0; i < N; i++) cerr << reach_parent[i] << ' ' << ord_index[i] << '\n';
 
 
	// cerr << "answering queries\n";
 
	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;
 
 
			int oldp = P[z];
			int newp = p;
 
			P[z] = p;
 
			// cerr << oldp << ' ' << newp << '\n';
 
			if(oldp == newp) 
			{
				// cerr << "waste\n";
				continue;
			}
 
			// cerr << "z = " << z << '\n';
 
 
 
			auto oldfind = occ[oldp].find(ord_index[z]);
 
			int of = *oldfind;
 
			auto oldfind_prev = oldfind;
			oldfind_prev--;
 
			int ofp = *oldfind_prev;
 
			auto oldfind_next = oldfind;
			oldfind_next++;
 
			// cerr << "ofp = "
 
			// cerr << "part1\n";
 
			MST.insert(of, ofp, -1);
			if(oldfind_next != occ[oldp].end())
			{
				int ofn = *oldfind_next;
				MST.insert(ofn, of, -1);
				MST.insert(ofn, ofp, +1);
			}
 
 
 
 
 
 
			auto newfind = occ[newp].lower_bound(ord_index[z]);
 
			int nfn = -1;
			if(newfind != occ[newp].end())
				nfn = *newfind;
 
			newfind--;
			int nfp = *newfind;
 
			// cerr << "part2\n";
 
			MST.insert(ord_index[z], nfp, +1);
			if(nfn != -1)
			{
				MST.insert(nfn, nfp, -1);
				MST.insert(nfn, ord_index[z], +1);
			}
 
 
			occ[oldp].erase(ord_index[z]);
			occ[newp].insert(ord_index[z]);
 
		}
		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;
			}
 
			// cerr << "z1 = " << z << '\n';
 
			for(int e = lg; e >= 0; e--)
				if(L[ anc[z][e] ] <= l)
					z = anc[z][e];
 
			// cerr << "z2 = " << z << '\n';
 
			int li = ord_index[z];
			int ri = ord_index[z] + subtree[z] - 1;
 
			// cerr << li << ' ' << ri << '\n';
 
			cout << MST.getcount(li, ri, li-1) << '\n';
		}
	}
}

Compilation message (stderr)

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

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