oj.uz

Submission #675012

# Submission time Handle Problem Language Result Execution time Memory
675012 2022-12-26T19:03:06 Z QwertyPi I want to be the very best too! (NOI17_pokemonmaster) C++14
27 / 100
 5000 ms 11580 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 = 3;
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
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 934 ms 6468 KB Output is correct
2 Correct 1190 ms 6524 KB Output is correct
3 Correct 1182 ms 6640 KB Output is correct
4 Correct 684 ms 6388 KB Output is correct
5 Correct 1135 ms 6516 KB Output is correct
6 Correct 2365 ms 6764 KB Output is correct
7 Correct 750 ms 6516 KB Output is correct
8 Correct 1073 ms 6344 KB Output is correct
9 Correct 802 ms 6380 KB Output is correct
10 Correct 1952 ms 6652 KB Output is correct
11 Correct 1256 ms 6540 KB Output is correct
12 Correct 2667 ms 7356 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 6468 KB Output is correct
2 Correct 51 ms 6616 KB Output is correct
3 Correct 49 ms 6760 KB Output is correct
4 Correct 51 ms 6692 KB Output is correct
5 Correct 54 ms 6804 KB Output is correct
6 Correct 66 ms 6848 KB Output is correct
7 Correct 62 ms 6920 KB Output is correct
8 Correct 88 ms 8404 KB Output is correct
9 Correct 59 ms 7100 KB Output is correct
10 Correct 94 ms 10360 KB Output is correct
11 Correct 106 ms 9048 KB Output is correct
12 Correct 131 ms 11580 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5019 ms 6660 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 934 ms 6468 KB Output is correct
2 Correct 1190 ms 6524 KB Output is correct
3 Correct 1182 ms 6640 KB Output is correct
4 Correct 684 ms 6388 KB Output is correct
5 Correct 1135 ms 6516 KB Output is correct
6 Correct 2365 ms 6764 KB Output is correct
7 Correct 750 ms 6516 KB Output is correct
8 Correct 1073 ms 6344 KB Output is correct
9 Correct 802 ms 6380 KB Output is correct
10 Correct 1952 ms 6652 KB Output is correct
11 Correct 1256 ms 6540 KB Output is correct
12 Correct 2667 ms 7356 KB Output is correct
13 Execution timed out 5063 ms 7400 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 934 ms 6468 KB Output is correct
2 Correct 1190 ms 6524 KB Output is correct
3 Correct 1182 ms 6640 KB Output is correct
4 Correct 684 ms 6388 KB Output is correct
5 Correct 1135 ms 6516 KB Output is correct
6 Correct 2365 ms 6764 KB Output is correct
7 Correct 750 ms 6516 KB Output is correct
8 Correct 1073 ms 6344 KB Output is correct
9 Correct 802 ms 6380 KB Output is correct
10 Correct 1952 ms 6652 KB Output is correct
11 Correct 1256 ms 6540 KB Output is correct
12 Correct 2667 ms 7356 KB Output is correct
13 Correct 52 ms 6468 KB Output is correct
14 Correct 51 ms 6616 KB Output is correct
15 Correct 49 ms 6760 KB Output is correct
16 Correct 51 ms 6692 KB Output is correct
17 Correct 54 ms 6804 KB Output is correct
18 Correct 66 ms 6848 KB Output is correct
19 Correct 62 ms 6920 KB Output is correct
20 Correct 88 ms 8404 KB Output is correct
21 Correct 59 ms 7100 KB Output is correct
22 Correct 94 ms 10360 KB Output is correct
23 Correct 106 ms 9048 KB Output is correct
24 Correct 131 ms 11580 KB Output is correct
25 Execution timed out 5019 ms 6660 KB Time limit exceeded
26 Halted 0 ms 0 KB -