oj.uz

Submission #675032

# Submission time Handle Problem Language Result Execution time Memory
675032 2022-12-26T19:52:51 Z QwertyPi I want to be the very best too! (NOI17_pokemonmaster) C++14
27 / 100
 5000 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 = 200;
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 52 ms 6332 KB Output is correct
2 Correct 61 ms 6408 KB Output is correct
3 Correct 101 ms 6340 KB Output is correct
4 Correct 52 ms 6396 KB Output is correct
5 Correct 60 ms 6340 KB Output is correct
6 Correct 80 ms 6404 KB Output is correct
7 Correct 51 ms 6368 KB Output is correct
8 Correct 57 ms 6400 KB Output is correct
9 Correct 60 ms 6464 KB Output is correct
10 Correct 88 ms 6276 KB Output is correct
11 Correct 66 ms 6396 KB Output is correct
12 Correct 97 ms 6340 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 6340 KB Output is correct
2 Correct 43 ms 6296 KB Output is correct
3 Correct 47 ms 6340 KB Output is correct
4 Correct 46 ms 6652 KB Output is correct
5 Correct 45 ms 6600 KB Output is correct
6 Correct 46 ms 6464 KB Output is correct
7 Correct 51 ms 6940 KB Output is correct
8 Correct 54 ms 6960 KB Output is correct
9 Correct 49 ms 6848 KB Output is correct
10 Correct 65 ms 6980 KB Output is correct
11 Correct 72 ms 6848 KB Output is correct
12 Correct 82 ms 6956 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2559 ms 7808 KB Output is correct
2 Correct 2441 ms 7556 KB Output is correct
3 Correct 2401 ms 7572 KB Output is correct
4 Correct 2447 ms 7948 KB Output is correct
5 Correct 2573 ms 7916 KB Output is correct
6 Correct 2482 ms 8096 KB Output is correct
7 Correct 4932 ms 8332 KB Output is correct
8 Correct 4789 ms 8344 KB Output is correct
9 Correct 4690 ms 8412 KB Output is correct
10 Execution timed out 5030 ms 8200 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 6332 KB Output is correct
2 Correct 61 ms 6408 KB Output is correct
3 Correct 101 ms 6340 KB Output is correct
4 Correct 52 ms 6396 KB Output is correct
5 Correct 60 ms 6340 KB Output is correct
6 Correct 80 ms 6404 KB Output is correct
7 Correct 51 ms 6368 KB Output is correct
8 Correct 57 ms 6400 KB Output is correct
9 Correct 60 ms 6464 KB Output is correct
10 Correct 88 ms 6276 KB Output is correct
11 Correct 66 ms 6396 KB Output is correct
12 Correct 97 ms 6340 KB Output is correct
13 Correct 2528 ms 7640 KB Output is correct
14 Correct 3481 ms 7672 KB Output is correct
15 Execution timed out 5019 ms 7500 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 6332 KB Output is correct
2 Correct 61 ms 6408 KB Output is correct
3 Correct 101 ms 6340 KB Output is correct
4 Correct 52 ms 6396 KB Output is correct
5 Correct 60 ms 6340 KB Output is correct
6 Correct 80 ms 6404 KB Output is correct
7 Correct 51 ms 6368 KB Output is correct
8 Correct 57 ms 6400 KB Output is correct
9 Correct 60 ms 6464 KB Output is correct
10 Correct 88 ms 6276 KB Output is correct
11 Correct 66 ms 6396 KB Output is correct
12 Correct 97 ms 6340 KB Output is correct
13 Correct 41 ms 6340 KB Output is correct
14 Correct 43 ms 6296 KB Output is correct
15 Correct 47 ms 6340 KB Output is correct
16 Correct 46 ms 6652 KB Output is correct
17 Correct 45 ms 6600 KB Output is correct
18 Correct 46 ms 6464 KB Output is correct
19 Correct 51 ms 6940 KB Output is correct
20 Correct 54 ms 6960 KB Output is correct
21 Correct 49 ms 6848 KB Output is correct
22 Correct 65 ms 6980 KB Output is correct
23 Correct 72 ms 6848 KB Output is correct
24 Correct 82 ms 6956 KB Output is correct
25 Correct 2559 ms 7808 KB Output is correct
26 Correct 2441 ms 7556 KB Output is correct
27 Correct 2401 ms 7572 KB Output is correct
28 Correct 2447 ms 7948 KB Output is correct
29 Correct 2573 ms 7916 KB Output is correct
30 Correct 2482 ms 8096 KB Output is correct
31 Correct 4932 ms 8332 KB Output is correct
32 Correct 4789 ms 8344 KB Output is correct
33 Correct 4690 ms 8412 KB Output is correct
34 Execution timed out 5030 ms 8200 KB Time limit exceeded
35 Halted 0 ms 0 KB -