oj.uz

Submission #522343

# Submission time Handle Problem Language Result Execution time Memory
522343 2022-02-04T16:05:03 Z blue I want to be the very best too! (NOI17_pokemonmaster) C++17
47 / 100
 4350 ms 524292 KB 
#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())
#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;
		}
	}
};

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{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);
		}
	}
}
 
 
 
 
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:370:5: warning: 'rt' may be used uninitialized in this function [-Wmaybe-uninitialized]
  370 |  dfs(rt);
      |  ~~~^~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 581 ms 183752 KB Output is correct
2 Correct 663 ms 230972 KB Output is correct
3 Correct 778 ms 316912 KB Output is correct
4 Correct 618 ms 184520 KB Output is correct
5 Correct 670 ms 226416 KB Output is correct
6 Correct 725 ms 307596 KB Output is correct
7 Correct 576 ms 175292 KB Output is correct
8 Correct 637 ms 213252 KB Output is correct
9 Correct 595 ms 180096 KB Output is correct
10 Correct 763 ms 312452 KB Output is correct
11 Correct 678 ms 246508 KB Output is correct
12 Correct 713 ms 289476 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 585 ms 182668 KB Output is correct
2 Correct 633 ms 227512 KB Output is correct
3 Correct 720 ms 306224 KB Output is correct
4 Correct 591 ms 182084 KB Output is correct
5 Correct 644 ms 223124 KB Output is correct
6 Correct 698 ms 297260 KB Output is correct
7 Correct 590 ms 173052 KB Output is correct
8 Correct 620 ms 209072 KB Output is correct
9 Correct 578 ms 177532 KB Output is correct
10 Correct 731 ms 304704 KB Output is correct
11 Correct 659 ms 240812 KB Output is correct
12 Correct 713 ms 282212 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1072 ms 179452 KB Output is correct
2 Correct 2290 ms 193156 KB Output is correct
3 Correct 3076 ms 200260 KB Output is correct
4 Correct 3037 ms 199440 KB Output is correct
5 Correct 2265 ms 193364 KB Output is correct
6 Correct 1064 ms 174268 KB Output is correct
7 Correct 2339 ms 191540 KB Output is correct
8 Correct 2255 ms 192024 KB Output is correct
9 Correct 2282 ms 191904 KB Output is correct
10 Correct 2246 ms 191988 KB Output is correct
11 Correct 2242 ms 191708 KB Output is correct
12 Correct 2250 ms 191640 KB Output is correct

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 581 ms 183752 KB Output is correct
2 Correct 663 ms 230972 KB Output is correct
3 Correct 778 ms 316912 KB Output is correct
4 Correct 618 ms 184520 KB Output is correct
5 Correct 670 ms 226416 KB Output is correct
6 Correct 725 ms 307596 KB Output is correct
7 Correct 576 ms 175292 KB Output is correct
8 Correct 637 ms 213252 KB Output is correct
9 Correct 595 ms 180096 KB Output is correct
10 Correct 763 ms 312452 KB Output is correct
11 Correct 678 ms 246508 KB Output is correct
12 Correct 713 ms 289476 KB Output is correct
13 Correct 1152 ms 192104 KB Output is correct
14 Correct 4350 ms 451252 KB Output is correct
15 Runtime error 2420 ms 524292 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 581 ms 183752 KB Output is correct
2 Correct 663 ms 230972 KB Output is correct
3 Correct 778 ms 316912 KB Output is correct
4 Correct 618 ms 184520 KB Output is correct
5 Correct 670 ms 226416 KB Output is correct
6 Correct 725 ms 307596 KB Output is correct
7 Correct 576 ms 175292 KB Output is correct
8 Correct 637 ms 213252 KB Output is correct
9 Correct 595 ms 180096 KB Output is correct
10 Correct 763 ms 312452 KB Output is correct
11 Correct 678 ms 246508 KB Output is correct
12 Correct 713 ms 289476 KB Output is correct
13 Correct 585 ms 182668 KB Output is correct
14 Correct 633 ms 227512 KB Output is correct
15 Correct 720 ms 306224 KB Output is correct
16 Correct 591 ms 182084 KB Output is correct
17 Correct 644 ms 223124 KB Output is correct
18 Correct 698 ms 297260 KB Output is correct
19 Correct 590 ms 173052 KB Output is correct
20 Correct 620 ms 209072 KB Output is correct
21 Correct 578 ms 177532 KB Output is correct
22 Correct 731 ms 304704 KB Output is correct
23 Correct 659 ms 240812 KB Output is correct
24 Correct 713 ms 282212 KB Output is correct
25 Correct 1072 ms 179452 KB Output is correct
26 Correct 2290 ms 193156 KB Output is correct
27 Correct 3076 ms 200260 KB Output is correct
28 Correct 3037 ms 199440 KB Output is correct
29 Correct 2265 ms 193364 KB Output is correct
30 Correct 1064 ms 174268 KB Output is correct
31 Correct 2339 ms 191540 KB Output is correct
32 Correct 2255 ms 192024 KB Output is correct
33 Correct 2282 ms 191904 KB Output is correct
34 Correct 2246 ms 191988 KB Output is correct
35 Correct 2242 ms 191708 KB Output is correct
36 Correct 2250 ms 191640 KB Output is correct
37 Correct 1152 ms 192104 KB Output is correct
38 Correct 4350 ms 451252 KB Output is correct
39 Runtime error 2420 ms 524292 KB Execution killed with signal 9
40 Halted 0 ms 0 KB -