oj.uz

Submission #522548

# Submission time Handle Problem Language Result Execution time Memory
522548 2022-02-05T06:48:54 Z blue I want to be the very best too! (NOI17_pokemonmaster) C++17
100 / 100
 3479 ms 319848 KB 
#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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 104376 KB Output is correct
2 Correct 170 ms 105124 KB Output is correct
3 Correct 184 ms 99948 KB Output is correct
4 Correct 181 ms 104976 KB Output is correct
5 Correct 163 ms 105148 KB Output is correct
6 Correct 179 ms 97548 KB Output is correct
7 Correct 168 ms 104236 KB Output is correct
8 Correct 153 ms 105028 KB Output is correct
9 Correct 143 ms 104500 KB Output is correct
10 Correct 172 ms 98748 KB Output is correct
11 Correct 189 ms 105020 KB Output is correct
12 Correct 192 ms 81696 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 103544 KB Output is correct
2 Correct 154 ms 103420 KB Output is correct
3 Correct 176 ms 96760 KB Output is correct
4 Correct 139 ms 103484 KB Output is correct
5 Correct 150 ms 103684 KB Output is correct
6 Correct 165 ms 94232 KB Output is correct
7 Correct 143 ms 102164 KB Output is correct
8 Correct 163 ms 102208 KB Output is correct
9 Correct 175 ms 102204 KB Output is correct
10 Correct 182 ms 95240 KB Output is correct
11 Correct 172 ms 101808 KB Output is correct
12 Correct 159 ms 78180 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 378 ms 107972 KB Output is correct
2 Correct 592 ms 118460 KB Output is correct
3 Correct 695 ms 123744 KB Output is correct
4 Correct 713 ms 123412 KB Output is correct
5 Correct 601 ms 118956 KB Output is correct
6 Correct 397 ms 105512 KB Output is correct
7 Correct 665 ms 117220 KB Output is correct
8 Correct 722 ms 117296 KB Output is correct
9 Correct 588 ms 117248 KB Output is correct
10 Correct 587 ms 117436 KB Output is correct
11 Correct 595 ms 117072 KB Output is correct
12 Correct 675 ms 116984 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 104376 KB Output is correct
2 Correct 170 ms 105124 KB Output is correct
3 Correct 184 ms 99948 KB Output is correct
4 Correct 181 ms 104976 KB Output is correct
5 Correct 163 ms 105148 KB Output is correct
6 Correct 179 ms 97548 KB Output is correct
7 Correct 168 ms 104236 KB Output is correct
8 Correct 153 ms 105028 KB Output is correct
9 Correct 143 ms 104500 KB Output is correct
10 Correct 172 ms 98748 KB Output is correct
11 Correct 189 ms 105020 KB Output is correct
12 Correct 192 ms 81696 KB Output is correct
13 Correct 428 ms 110648 KB Output is correct
14 Correct 1684 ms 197444 KB Output is correct
15 Correct 3335 ms 319848 KB Output is correct
16 Correct 1026 ms 148008 KB Output is correct
17 Correct 1625 ms 193300 KB Output is correct
18 Correct 807 ms 119868 KB Output is correct
19 Correct 218 ms 105916 KB Output is correct
20 Correct 1473 ms 179756 KB Output is correct
21 Correct 538 ms 121228 KB Output is correct
22 Correct 2231 ms 236444 KB Output is correct
23 Correct 1811 ms 209904 KB Output is correct
24 Correct 1807 ms 186720 KB Output is correct

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 104376 KB Output is correct
2 Correct 170 ms 105124 KB Output is correct
3 Correct 184 ms 99948 KB Output is correct
4 Correct 181 ms 104976 KB Output is correct
5 Correct 163 ms 105148 KB Output is correct
6 Correct 179 ms 97548 KB Output is correct
7 Correct 168 ms 104236 KB Output is correct
8 Correct 153 ms 105028 KB Output is correct
9 Correct 143 ms 104500 KB Output is correct
10 Correct 172 ms 98748 KB Output is correct
11 Correct 189 ms 105020 KB Output is correct
12 Correct 192 ms 81696 KB Output is correct
13 Correct 133 ms 103544 KB Output is correct
14 Correct 154 ms 103420 KB Output is correct
15 Correct 176 ms 96760 KB Output is correct
16 Correct 139 ms 103484 KB Output is correct
17 Correct 150 ms 103684 KB Output is correct
18 Correct 165 ms 94232 KB Output is correct
19 Correct 143 ms 102164 KB Output is correct
20 Correct 163 ms 102208 KB Output is correct
21 Correct 175 ms 102204 KB Output is correct
22 Correct 182 ms 95240 KB Output is correct
23 Correct 172 ms 101808 KB Output is correct
24 Correct 159 ms 78180 KB Output is correct
25 Correct 378 ms 107972 KB Output is correct
26 Correct 592 ms 118460 KB Output is correct
27 Correct 695 ms 123744 KB Output is correct
28 Correct 713 ms 123412 KB Output is correct
29 Correct 601 ms 118956 KB Output is correct
30 Correct 397 ms 105512 KB Output is correct
31 Correct 665 ms 117220 KB Output is correct
32 Correct 722 ms 117296 KB Output is correct
33 Correct 588 ms 117248 KB Output is correct
34 Correct 587 ms 117436 KB Output is correct
35 Correct 595 ms 117072 KB Output is correct
36 Correct 675 ms 116984 KB Output is correct
37 Correct 428 ms 110648 KB Output is correct
38 Correct 1684 ms 197444 KB Output is correct
39 Correct 3335 ms 319848 KB Output is correct
40 Correct 1026 ms 148008 KB Output is correct
41 Correct 1625 ms 193300 KB Output is correct
42 Correct 807 ms 119868 KB Output is correct
43 Correct 218 ms 105916 KB Output is correct
44 Correct 1473 ms 179756 KB Output is correct
45 Correct 538 ms 121228 KB Output is correct
46 Correct 2231 ms 236444 KB Output is correct
47 Correct 1811 ms 209904 KB Output is correct
48 Correct 1807 ms 186720 KB Output is correct
49 Correct 457 ms 110264 KB Output is correct
50 Correct 1687 ms 197268 KB Output is correct
51 Correct 3479 ms 319228 KB Output is correct
52 Correct 1118 ms 147076 KB Output is correct
53 Correct 1670 ms 193608 KB Output is correct
54 Correct 901 ms 117164 KB Output is correct
55 Correct 286 ms 103908 KB Output is correct
56 Correct 1472 ms 178892 KB Output is correct
57 Correct 591 ms 119444 KB Output is correct
58 Correct 2319 ms 235124 KB Output is correct
59 Correct 1906 ms 208156 KB Output is correct
60 Correct 1966 ms 185600 KB Output is correct