oj.uz

답안 #675028

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
675028 2022-12-26T19:44:07 Z QwertyPi I want to be the very best too! (NOI17_pokemonmaster) C++14
47 / 100
 5000 ms 10080 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], 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]]++, ans[i] = 1;
	}
	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]) ans[x] += info[x][i.fi] == 0 && i.se != 0, 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;
				dsu.info[pos][change[_l + k].fi]--;
				if(dsu.info[pos][change[_l + k].fi] == 0) dsu.ans[pos]--;
				dsu.info[pos][change[_l + k].se]++;
				if(dsu.info[pos][change[_l + k].se] == 1) dsu.ans[pos]++;
			}
		}
		if(l[Q[ri].x * m + Q[ri].y] <= Q[ri].v){
			ans[i] = dsu.ans[pos];
		}
		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.ans[pos]--;
				dsu.info[pos][change[_l + k].fi]++;
				if(dsu.info[pos][change[_l + k].fi] == 1) dsu.ans[pos]++;
			}
		}
	}
}

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

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 6596 KB Output is correct
2 Correct 55 ms 6592 KB Output is correct
3 Correct 66 ms 6628 KB Output is correct
4 Correct 37 ms 6600 KB Output is correct
5 Correct 55 ms 6580 KB Output is correct
6 Correct 53 ms 6596 KB Output is correct
7 Correct 36 ms 6544 KB Output is correct
8 Correct 53 ms 6596 KB Output is correct
9 Correct 40 ms 6572 KB Output is correct
10 Correct 85 ms 6528 KB Output is correct
11 Correct 62 ms 6616 KB Output is correct
12 Correct 104 ms 6512 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 6528 KB Output is correct
2 Correct 43 ms 6572 KB Output is correct
3 Correct 53 ms 6576 KB Output is correct
4 Correct 41 ms 6824 KB Output is correct
5 Correct 43 ms 6828 KB Output is correct
6 Correct 48 ms 6680 KB Output is correct
7 Correct 51 ms 7048 KB Output is correct
8 Correct 56 ms 7152 KB Output is correct
9 Correct 51 ms 7152 KB Output is correct
10 Correct 76 ms 7136 KB Output is correct
11 Correct 61 ms 7160 KB Output is correct
12 Correct 73 ms 7100 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 871 ms 8024 KB Output is correct
2 Correct 1014 ms 7992 KB Output is correct
3 Correct 823 ms 7808 KB Output is correct
4 Correct 824 ms 8160 KB Output is correct
5 Correct 1076 ms 8100 KB Output is correct
6 Correct 882 ms 8164 KB Output is correct
7 Correct 1603 ms 8352 KB Output is correct
8 Correct 1611 ms 8472 KB Output is correct
9 Correct 1629 ms 8524 KB Output is correct
10 Correct 1639 ms 8440 KB Output is correct
11 Correct 1682 ms 8408 KB Output is correct
12 Correct 1658 ms 8636 KB Output is correct

Subtask #4
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 6596 KB Output is correct
2 Correct 55 ms 6592 KB Output is correct
3 Correct 66 ms 6628 KB Output is correct
4 Correct 37 ms 6600 KB Output is correct
5 Correct 55 ms 6580 KB Output is correct
6 Correct 53 ms 6596 KB Output is correct
7 Correct 36 ms 6544 KB Output is correct
8 Correct 53 ms 6596 KB Output is correct
9 Correct 40 ms 6572 KB Output is correct
10 Correct 85 ms 6528 KB Output is correct
11 Correct 62 ms 6616 KB Output is correct
12 Correct 104 ms 6512 KB Output is correct
13 Correct 942 ms 7892 KB Output is correct
14 Correct 2833 ms 7960 KB Output is correct
15 Correct 4449 ms 8028 KB Output is correct
16 Correct 943 ms 8048 KB Output is correct
17 Correct 2709 ms 8040 KB Output is correct
18 Correct 2578 ms 8400 KB Output is correct
19 Correct 919 ms 9952 KB Output is correct
20 Correct 2214 ms 10080 KB Output is correct
21 Correct 1073 ms 10060 KB Output is correct
22 Execution timed out 5059 ms 9836 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 6596 KB Output is correct
2 Correct 55 ms 6592 KB Output is correct
3 Correct 66 ms 6628 KB Output is correct
4 Correct 37 ms 6600 KB Output is correct
5 Correct 55 ms 6580 KB Output is correct
6 Correct 53 ms 6596 KB Output is correct
7 Correct 36 ms 6544 KB Output is correct
8 Correct 53 ms 6596 KB Output is correct
9 Correct 40 ms 6572 KB Output is correct
10 Correct 85 ms 6528 KB Output is correct
11 Correct 62 ms 6616 KB Output is correct
12 Correct 104 ms 6512 KB Output is correct
13 Correct 42 ms 6528 KB Output is correct
14 Correct 43 ms 6572 KB Output is correct
15 Correct 53 ms 6576 KB Output is correct
16 Correct 41 ms 6824 KB Output is correct
17 Correct 43 ms 6828 KB Output is correct
18 Correct 48 ms 6680 KB Output is correct
19 Correct 51 ms 7048 KB Output is correct
20 Correct 56 ms 7152 KB Output is correct
21 Correct 51 ms 7152 KB Output is correct
22 Correct 76 ms 7136 KB Output is correct
23 Correct 61 ms 7160 KB Output is correct
24 Correct 73 ms 7100 KB Output is correct
25 Correct 871 ms 8024 KB Output is correct
26 Correct 1014 ms 7992 KB Output is correct
27 Correct 823 ms 7808 KB Output is correct
28 Correct 824 ms 8160 KB Output is correct
29 Correct 1076 ms 8100 KB Output is correct
30 Correct 882 ms 8164 KB Output is correct
31 Correct 1603 ms 8352 KB Output is correct
32 Correct 1611 ms 8472 KB Output is correct
33 Correct 1629 ms 8524 KB Output is correct
34 Correct 1639 ms 8440 KB Output is correct
35 Correct 1682 ms 8408 KB Output is correct
36 Correct 1658 ms 8636 KB Output is correct
37 Correct 942 ms 7892 KB Output is correct
38 Correct 2833 ms 7960 KB Output is correct
39 Correct 4449 ms 8028 KB Output is correct
40 Correct 943 ms 8048 KB Output is correct
41 Correct 2709 ms 8040 KB Output is correct
42 Correct 2578 ms 8400 KB Output is correct
43 Correct 919 ms 9952 KB Output is correct
44 Correct 2214 ms 10080 KB Output is correct
45 Correct 1073 ms 10060 KB Output is correct
46 Execution timed out 5059 ms 9836 KB Time limit exceeded
47 Halted 0 ms 0 KB -