oj.uz

Submission #674997

# Submission time Handle Problem Language Result Execution time Memory
674997 2022-12-26T18:37:03 Z QwertyPi I want to be the very best too! (NOI17_pokemonmaster) C++14
16 / 100
 542 ms 14912 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[MAXN];
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[k].fi]--;
				if(dsu.info[pos][change[k].fi] == 0) dsu.info[pos].erase(change[k].fi);
				dsu.info[pos][change[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[k].se]--;
				if(dsu.info[pos][change[k].se] == 0) dsu.info[pos].erase(change[k].se);
				dsu.info[pos][change[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];
		}
	}
	map<int, int> upd;
	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 6724 KB Output is correct
2 Correct 51 ms 7016 KB Output is correct
3 Correct 57 ms 7256 KB Output is correct
4 Correct 45 ms 7024 KB Output is correct
5 Correct 51 ms 6976 KB Output is correct
6 Correct 45 ms 7168 KB Output is correct
7 Correct 35 ms 6876 KB Output is correct
8 Correct 44 ms 6944 KB Output is correct
9 Correct 40 ms 6980 KB Output is correct
10 Correct 73 ms 7184 KB Output is correct
11 Correct 63 ms 7036 KB Output is correct
12 Incorrect 92 ms 7796 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 40 ms 6908 KB Output is correct
2 Correct 42 ms 6980 KB Output is correct
3 Correct 45 ms 7624 KB Output is correct
4 Correct 41 ms 7496 KB Output is correct
5 Correct 53 ms 7480 KB Output is correct
6 Correct 45 ms 7692 KB Output is correct
7 Correct 49 ms 7724 KB Output is correct
8 Correct 57 ms 9080 KB Output is correct
9 Correct 47 ms 7804 KB Output is correct
10 Correct 75 ms 11120 KB Output is correct
11 Correct 59 ms 9804 KB Output is correct
12 Correct 71 ms 12268 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 542 ms 14912 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 6724 KB Output is correct
2 Correct 51 ms 7016 KB Output is correct
3 Correct 57 ms 7256 KB Output is correct
4 Correct 45 ms 7024 KB Output is correct
5 Correct 51 ms 6976 KB Output is correct
6 Correct 45 ms 7168 KB Output is correct
7 Correct 35 ms 6876 KB Output is correct
8 Correct 44 ms 6944 KB Output is correct
9 Correct 40 ms 6980 KB Output is correct
10 Correct 73 ms 7184 KB Output is correct
11 Correct 63 ms 7036 KB Output is correct
12 Incorrect 92 ms 7796 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 6724 KB Output is correct
2 Correct 51 ms 7016 KB Output is correct
3 Correct 57 ms 7256 KB Output is correct
4 Correct 45 ms 7024 KB Output is correct
5 Correct 51 ms 6976 KB Output is correct
6 Correct 45 ms 7168 KB Output is correct
7 Correct 35 ms 6876 KB Output is correct
8 Correct 44 ms 6944 KB Output is correct
9 Correct 40 ms 6980 KB Output is correct
10 Correct 73 ms 7184 KB Output is correct
11 Correct 63 ms 7036 KB Output is correct
12 Incorrect 92 ms 7796 KB Output isn't correct
13 Halted 0 ms 0 KB -