oj.uz

Submission #675013

# Submission time Handle Problem Language Result Execution time Memory
675013 2022-12-26T19:03:52 Z QwertyPi I want to be the very best too! (NOI17_pokemonmaster) C++14
36 / 100
 1379 ms 11516 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(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 35 ms 6392 KB Output is correct
2 Correct 49 ms 6376 KB Output is correct
3 Correct 57 ms 6664 KB Output is correct
4 Correct 36 ms 6380 KB Output is correct
5 Correct 52 ms 6412 KB Output is correct
6 Correct 45 ms 6612 KB Output is correct
7 Correct 35 ms 6360 KB Output is correct
8 Correct 45 ms 6348 KB Output is correct
9 Correct 39 ms 6328 KB Output is correct
10 Correct 69 ms 6680 KB Output is correct
11 Correct 50 ms 6476 KB Output is correct
12 Incorrect 91 ms 7260 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 6516 KB Output is correct
2 Correct 42 ms 6596 KB Output is correct
3 Correct 44 ms 6776 KB Output is correct
4 Correct 42 ms 6648 KB Output is correct
5 Correct 44 ms 6776 KB Output is correct
6 Correct 44 ms 6848 KB Output is correct
7 Correct 48 ms 6852 KB Output is correct
8 Correct 57 ms 8272 KB Output is correct
9 Correct 51 ms 7108 KB Output is correct
10 Correct 68 ms 10316 KB Output is correct
11 Correct 72 ms 9040 KB Output is correct
12 Correct 68 ms 11516 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 704 ms 7892 KB Output is correct
2 Correct 861 ms 9900 KB Output is correct
3 Correct 674 ms 9536 KB Output is correct
4 Correct 655 ms 9832 KB Output is correct
5 Correct 885 ms 10044 KB Output is correct
6 Correct 719 ms 10448 KB Output is correct
7 Correct 1302 ms 10440 KB Output is correct
8 Correct 1317 ms 10560 KB Output is correct
9 Correct 1329 ms 10764 KB Output is correct
10 Correct 1322 ms 10716 KB Output is correct
11 Correct 1379 ms 10680 KB Output is correct
12 Correct 1300 ms 10632 KB Output is correct

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 6392 KB Output is correct
2 Correct 49 ms 6376 KB Output is correct
3 Correct 57 ms 6664 KB Output is correct
4 Correct 36 ms 6380 KB Output is correct
5 Correct 52 ms 6412 KB Output is correct
6 Correct 45 ms 6612 KB Output is correct
7 Correct 35 ms 6360 KB Output is correct
8 Correct 45 ms 6348 KB Output is correct
9 Correct 39 ms 6328 KB Output is correct
10 Correct 69 ms 6680 KB Output is correct
11 Correct 50 ms 6476 KB Output is correct
12 Incorrect 91 ms 7260 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 6392 KB Output is correct
2 Correct 49 ms 6376 KB Output is correct
3 Correct 57 ms 6664 KB Output is correct
4 Correct 36 ms 6380 KB Output is correct
5 Correct 52 ms 6412 KB Output is correct
6 Correct 45 ms 6612 KB Output is correct
7 Correct 35 ms 6360 KB Output is correct
8 Correct 45 ms 6348 KB Output is correct
9 Correct 39 ms 6328 KB Output is correct
10 Correct 69 ms 6680 KB Output is correct
11 Correct 50 ms 6476 KB Output is correct
12 Incorrect 91 ms 7260 KB Output isn't correct
13 Halted 0 ms 0 KB -