#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[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; int 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++;
| ~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
900 ms |
6448 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
50 ms |
6476 KB |
Output is correct |
| 2 |
Correct |
50 ms |
6612 KB |
Output is correct |
| 3 |
Correct |
49 ms |
6756 KB |
Output is correct |
| 4 |
Correct |
48 ms |
6644 KB |
Output is correct |
| 5 |
Correct |
53 ms |
6716 KB |
Output is correct |
| 6 |
Correct |
65 ms |
6884 KB |
Output is correct |
| 7 |
Correct |
60 ms |
6836 KB |
Output is correct |
| 8 |
Correct |
82 ms |
8264 KB |
Output is correct |
| 9 |
Incorrect |
60 ms |
7104 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5045 ms |
6888 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
900 ms |
6448 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
900 ms |
6448 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
