oj.uz

Submission #675033

# Submission time Handle Problem Language Result Execution time Memory
675033 2022-12-26T19:53:31 Z QwertyPi I want to be the very best too! (NOI17_pokemonmaster) C++14
47 / 100
 2735 ms 8412 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 = 800;
int l[MAXN], p[MAXN], tp[MAXN];
int ans[MAXQ];

struct DSU{
	int dsu[MAXN], ans[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;
		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;
				auto ptr = dsu.info[pos].find(change[_l + k].fi); ptr->se--;
				if(ptr->se == 0) dsu.info[pos].erase(ptr);
				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(int k = 0; k < ri; k++){
			if(Q[k].t == 1){
				if(dsu.f(Q[k].x * m + Q[k].y) != pos) continue;
				auto ptr = dsu.info[pos].find(change[_l + k].se); ptr->se--;
				if(ptr->se == 0) dsu.info[pos].erase(ptr);
				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:62: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]
   62 |  for(int j = 0; j < Q2.size(); j++){
      |                 ~~^~~~~~~~~~~
pokemonmaster.cpp:63:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |   while(eid < E.size() && E[eid].w <= Q2[j].fi) dsu.g(E[eid].u, E[eid].v), eid++;
      |         ~~~~^~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 6340 KB Output is correct
2 Correct 49 ms 6452 KB Output is correct
3 Correct 58 ms 6328 KB Output is correct
4 Correct 41 ms 6328 KB Output is correct
5 Correct 48 ms 6364 KB Output is correct
6 Correct 55 ms 6452 KB Output is correct
7 Correct 41 ms 6436 KB Output is correct
8 Correct 48 ms 6340 KB Output is correct
9 Correct 43 ms 6424 KB Output is correct
10 Correct 70 ms 6440 KB Output is correct
11 Correct 58 ms 6384 KB Output is correct
12 Correct 78 ms 6436 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 6364 KB Output is correct
2 Correct 44 ms 6308 KB Output is correct
3 Correct 48 ms 6352 KB Output is correct
4 Correct 42 ms 6536 KB Output is correct
5 Correct 45 ms 6592 KB Output is correct
6 Correct 48 ms 6580 KB Output is correct
7 Correct 52 ms 6852 KB Output is correct
8 Correct 60 ms 6844 KB Output is correct
9 Correct 54 ms 6844 KB Output is correct
10 Correct 64 ms 6876 KB Output is correct
11 Correct 57 ms 6936 KB Output is correct
12 Correct 69 ms 6940 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 925 ms 7720 KB Output is correct
2 Correct 1076 ms 7880 KB Output is correct
3 Correct 855 ms 7636 KB Output is correct
4 Correct 883 ms 7784 KB Output is correct
5 Correct 1102 ms 7964 KB Output is correct
6 Correct 987 ms 8160 KB Output is correct
7 Correct 1755 ms 8228 KB Output is correct
8 Correct 1652 ms 8388 KB Output is correct
9 Correct 1656 ms 8236 KB Output is correct
10 Correct 1720 ms 8404 KB Output is correct
11 Correct 1661 ms 8400 KB Output is correct
12 Correct 1654 ms 8412 KB Output is correct

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 6340 KB Output is correct
2 Correct 49 ms 6452 KB Output is correct
3 Correct 58 ms 6328 KB Output is correct
4 Correct 41 ms 6328 KB Output is correct
5 Correct 48 ms 6364 KB Output is correct
6 Correct 55 ms 6452 KB Output is correct
7 Correct 41 ms 6436 KB Output is correct
8 Correct 48 ms 6340 KB Output is correct
9 Correct 43 ms 6424 KB Output is correct
10 Correct 70 ms 6440 KB Output is correct
11 Correct 58 ms 6384 KB Output is correct
12 Correct 78 ms 6436 KB Output is correct
13 Correct 899 ms 7804 KB Output is correct
14 Correct 1759 ms 7800 KB Output is correct
15 Incorrect 2735 ms 7836 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 6340 KB Output is correct
2 Correct 49 ms 6452 KB Output is correct
3 Correct 58 ms 6328 KB Output is correct
4 Correct 41 ms 6328 KB Output is correct
5 Correct 48 ms 6364 KB Output is correct
6 Correct 55 ms 6452 KB Output is correct
7 Correct 41 ms 6436 KB Output is correct
8 Correct 48 ms 6340 KB Output is correct
9 Correct 43 ms 6424 KB Output is correct
10 Correct 70 ms 6440 KB Output is correct
11 Correct 58 ms 6384 KB Output is correct
12 Correct 78 ms 6436 KB Output is correct
13 Correct 49 ms 6364 KB Output is correct
14 Correct 44 ms 6308 KB Output is correct
15 Correct 48 ms 6352 KB Output is correct
16 Correct 42 ms 6536 KB Output is correct
17 Correct 45 ms 6592 KB Output is correct
18 Correct 48 ms 6580 KB Output is correct
19 Correct 52 ms 6852 KB Output is correct
20 Correct 60 ms 6844 KB Output is correct
21 Correct 54 ms 6844 KB Output is correct
22 Correct 64 ms 6876 KB Output is correct
23 Correct 57 ms 6936 KB Output is correct
24 Correct 69 ms 6940 KB Output is correct
25 Correct 925 ms 7720 KB Output is correct
26 Correct 1076 ms 7880 KB Output is correct
27 Correct 855 ms 7636 KB Output is correct
28 Correct 883 ms 7784 KB Output is correct
29 Correct 1102 ms 7964 KB Output is correct
30 Correct 987 ms 8160 KB Output is correct
31 Correct 1755 ms 8228 KB Output is correct
32 Correct 1652 ms 8388 KB Output is correct
33 Correct 1656 ms 8236 KB Output is correct
34 Correct 1720 ms 8404 KB Output is correct
35 Correct 1661 ms 8400 KB Output is correct
36 Correct 1654 ms 8412 KB Output is correct
37 Correct 899 ms 7804 KB Output is correct
38 Correct 1759 ms 7800 KB Output is correct
39 Incorrect 2735 ms 7836 KB Output isn't correct
40 Halted 0 ms 0 KB -