oj.uz

Submission #675016

# Submission time Handle Problem Language Result Execution time Memory
675016 2022-12-26T19:20:25 Z QwertyPi I want to be the very best too! (NOI17_pokemonmaster) C++14
36 / 100
 1557 ms 14268 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;

const int MAXN = 5e4 + 11, MAXQ = 1e5 + 11;
const int SQ = 1000;
int l[MAXN], p[MAXN], tp[MAXN];
int ans[MAXQ];

struct DSU{
	int dsu[MAXN];
	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]]++;
	}
	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]) info[x][i.fi] += i.se;
		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.info[pos].erase(change[_l + k].fi);
				dsu.info[pos][change[_l + k].se]++;
			}
		}
		if(l[Q[ri].x * m + Q[ri].y] <= Q[ri].v){
			ans[i] = dsu.info[pos].size();
			for(auto i : dsu.info[pos]){
				assert(i.se > 0);
			}
		}
		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.info[pos].erase(change[_l + k].se);
				dsu.info[pos][change[_l + k].fi]++;
			}
		}
	}
}

int32_t main(){
	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

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

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 6340 KB Output is correct
2 Correct 50 ms 6440 KB Output is correct
3 Correct 63 ms 6660 KB Output is correct
4 Correct 36 ms 6436 KB Output is correct
5 Correct 48 ms 6396 KB Output is correct
6 Correct 95 ms 6720 KB Output is correct
7 Correct 36 ms 6352 KB Output is correct
8 Correct 46 ms 6460 KB Output is correct
9 Correct 38 ms 6436 KB Output is correct
10 Correct 92 ms 6584 KB Output is correct
11 Correct 52 ms 6340 KB Output is correct
12 Runtime error 56 ms 14268 KB Execution killed with signal 6
13 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 6452 KB Output is correct
2 Correct 40 ms 6516 KB Output is correct
3 Correct 45 ms 6824 KB Output is correct
4 Correct 43 ms 6632 KB Output is correct
5 Correct 42 ms 6784 KB Output is correct
6 Correct 44 ms 6888 KB Output is correct
7 Correct 47 ms 6916 KB Output is correct
8 Correct 55 ms 8272 KB Output is correct
9 Correct 45 ms 7172 KB Output is correct
10 Correct 64 ms 10332 KB Output is correct
11 Correct 57 ms 8956 KB Output is correct
12 Correct 68 ms 11504 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 703 ms 7812 KB Output is correct
2 Correct 840 ms 7872 KB Output is correct
3 Correct 652 ms 7828 KB Output is correct
4 Correct 668 ms 7944 KB Output is correct
5 Correct 891 ms 8156 KB Output is correct
6 Correct 714 ms 8000 KB Output is correct
7 Correct 1466 ms 8448 KB Output is correct
8 Correct 1490 ms 8480 KB Output is correct
9 Correct 1505 ms 8492 KB Output is correct
10 Correct 1483 ms 8412 KB Output is correct
11 Correct 1499 ms 8388 KB Output is correct
12 Correct 1557 ms 8444 KB Output is correct

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 6340 KB Output is correct
2 Correct 50 ms 6440 KB Output is correct
3 Correct 63 ms 6660 KB Output is correct
4 Correct 36 ms 6436 KB Output is correct
5 Correct 48 ms 6396 KB Output is correct
6 Correct 95 ms 6720 KB Output is correct
7 Correct 36 ms 6352 KB Output is correct
8 Correct 46 ms 6460 KB Output is correct
9 Correct 38 ms 6436 KB Output is correct
10 Correct 92 ms 6584 KB Output is correct
11 Correct 52 ms 6340 KB Output is correct
12 Runtime error 56 ms 14268 KB Execution killed with signal 6
13 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 6340 KB Output is correct
2 Correct 50 ms 6440 KB Output is correct
3 Correct 63 ms 6660 KB Output is correct
4 Correct 36 ms 6436 KB Output is correct
5 Correct 48 ms 6396 KB Output is correct
6 Correct 95 ms 6720 KB Output is correct
7 Correct 36 ms 6352 KB Output is correct
8 Correct 46 ms 6460 KB Output is correct
9 Correct 38 ms 6436 KB Output is correct
10 Correct 92 ms 6584 KB Output is correct
11 Correct 52 ms 6340 KB Output is correct
12 Runtime error 56 ms 14268 KB Execution killed with signal 6
13 Halted 0 ms 0 KB -