Submission #675035

#	Time	Username	Problem	Language	Result	Execution time	Memory
675035		QwertyPi	I want to be the very best too! (NOI17_pokemonmaster)	C++14	100 / 100	4562 ms	14724 KiB

pokemonmaster

#include <bits/stdc++.h>
#define fi first
#define se second
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
 
const int MAXN = 5e4 + 11, MAXQ = 1e5 + 11;
const int SQ = 800;
int l[MAXN], p[MAXN], tp[MAXN];
int ans[MAXQ];
 
struct DSU{
	int dsu[MAXN], ans[MAXN];
	unordered_map<int, int> info[MAXN];
	void init(int n){
		for(int i = 0; i < n; i++) dsu[i] = i;
		for(int i = 0; i < n; i++) info[i].clear(), info[i][p[i]]++, ans[i] = 1;
	}
	int f(int x){
		return dsu[x] == x ? x : dsu[x] = f(dsu[x]);
	}
	void g(int x, int y){
		x = f(x), y = f(y);
		if(x == y) return;
		if(info[x].size() < info[y].size()) swap(x, y);
		for(auto i : info[y]) ans[x] += info[x][i.fi] == 0 && i.se != 0, info[x][i.fi] += i.se;
		info[y].clear();
		dsu[y] = x;
	}
} dsu;
 
struct qry{
	int t, x, y, v, i; 
};
 
struct edge{
	int u, v, w;
	bool operator< (const edge& o) const {
		return w < o.w;
	}
};
int n, m, q;
pair<int, int> change[MAXQ];
vector<edge> E; int eid = 0;
void solve(vector<qry> Q){
	eid = 0;
	int _l = Q[0].i;
	dsu.init(n * m);
	for(int i = 0; i < n * m; i++) tp[i] = p[i];
	for(auto q : Q){
		if(q.t == 1){
			change[q.i] = {tp[q.x * m + q.y], q.v};
			tp[q.x * m + q.y] = q.v;
		}
	}
	vector<pair<int, int>> Q2;
	for(auto q : Q){
		if(q.t == 2){
			Q2.push_back({q.v, q.i});
		}
	}
	sort(Q2.begin(), Q2.end());
	for(int j = 0; j < Q2.size(); j++){
		while(eid < E.size() && E[eid].w <= Q2[j].fi) dsu.g(E[eid].u, E[eid].v), eid++;
		int i = Q2[j].se, ri = i - _l;
		int pos = dsu.f(Q[ri].x * m + Q[ri].y);
		for(int k = 0; k < ri; k++){
			if(Q[k].t == 1){
				if(dsu.f(Q[k].x * m + Q[k].y) != pos) continue;
				dsu.info[pos][change[_l + k].fi]--;
				if(dsu.info[pos][change[_l + k].fi] == 0) dsu.ans[pos]--;
				dsu.info[pos][change[_l + k].se]++;
				if(dsu.info[pos][change[_l + k].se] == 1) dsu.ans[pos]++;
			}
		}
		if(l[Q[ri].x * m + Q[ri].y] <= Q[ri].v){
			ans[i] = dsu.ans[pos];
		}
		for(int k = 0; k < ri; k++){
			if(Q[k].t == 1){
				if(dsu.f(Q[k].x * m + Q[k].y) != pos) continue;
				dsu.info[pos][change[_l + k].se]--;
				if(dsu.info[pos][change[_l + k].se] == 0) dsu.ans[pos]--;
				dsu.info[pos][change[_l + k].fi]++;
				if(dsu.info[pos][change[_l + k].fi] == 1) dsu.ans[pos]++;
			}
		}
	}
}
 
int32_t main(){
	cin.tie(0); cout.tie(0)->sync_with_stdio(false);
	cin >> n >> m >> q;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			cin >> l[i * m + j];
		}
	}
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m - 1; j++){
			int u = i * m + j, v = i * m + j + 1;
			E.push_back({u, v, max(l[u], l[v])});
		}
	}
	for(int i = 0; i < n - 1; i++){
		for(int j = 0; j < m; j++){
			int u = i * m + j, v = (i + 1) * m + j;
			E.push_back({u, v, max(l[u], l[v])});
		}
	}
	sort(E.begin(), E.end());
	
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			cin >> p[i * m + j];
		}
	}
	for(int i = 0; i < q; i += SQ){
		vector<qry> Q;
		for(int j = i; j < min(i + SQ, q); j++){
			int t, x, y, v;
			cin >> t >> y >> x >> v;
			x--; y--;
			Q.push_back({t, x, y, v, j});
		}
		solve(Q);
		for(auto q : Q){
			if(q.t == 1) p[q.x * m + q.y] = q.v;
		}
		for(int j = i; j < min(i + SQ, q); j++){
			if(Q[j - i].t == 2){
				cout << ans[j] << endl;
			}
		}
	}
}

Compilation message (stderr)

pokemonmaster.cpp: In function 'void solve(std::vector<qry>)':
pokemonmaster.cpp:64:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |  for(int j = 0; j < Q2.size(); j++){
      |                 ~~^~~~~~~~~~~
pokemonmaster.cpp:65:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |   while(eid < E.size() && E[eid].w <= Q2[j].fi) dsu.g(E[eid].u, E[eid].v), eid++;
      |         ~~~~^~~~~~~~~~

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