#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
using vi = vector<int>;
using pii = pair<int, int>;
using vvi = vector<vi>;
using vpii = vector<pii>;
const int mx = 50'000;
const int lg = 16;
#define sz(x) int(x.size())
int R, C, Q;
int N;
vi L(mx), P(mx);
vi edge[mx];
void add_edge(int u, int v)
{
edge[u].push_back(v);
edge[v].push_back(u);
}
struct disjoint_set
{
vi parent = vi(mx);
vi subtree = vi(mx, 1);
vpii peak = vpii(mx);
disjoint_set()
{
for(int i = 0; i < mx; i++)
{
parent[i] = i;
peak[i] = {L[i], i};
}
}
int root(int u)
{
if(parent[u] == u) return u;
else return (parent[u] = root(parent[u]));
}
int getpeak(int u)
{
return peak[root(u)].second;
}
void join(int u, int v)
{
u = root(u);
v = root(v);
if(u == v) return;
if(subtree[u] < subtree[v]) swap(u, v);
parent[v] = u;
subtree[u] += subtree[v];
peak[u] = max(peak[u], peak[v]);
}
bool connected(int u, int v)
{
return root(u) == root(v);
}
};
vi reach_children[mx];
vi reach_parent(mx);
vvi anc(mx, vi(1+lg));
vi subtree(mx, 1);
vi ord(1, -1);
vi ord_index(mx, 0);
vi depth(mx, 0);
int o_ct = 0;
void dfs(int u)
{
ord.push_back(u);
ord_index[u] = ++o_ct;
for(int v : reach_children[u])
{
depth[v] = depth[u] + 1;
dfs(v);
subtree[u] += subtree[v];
}
}
int ancestor(int u, int k)
{
for(int e = 0; e <= lg; e++)
if(k & (1 << e))
u = anc[u][e];
return u;
}
int lca(int u, int v)
{
if(depth[u] > depth[v]) swap(u, v);
v = ancestor(v, depth[v] - depth[u]);
if(u == v) return u;
for(int e = lg; e >= 0; e--)
{
if(anc[u][e] != anc[v][e])
{
u = anc[u][e];
v = anc[v][e];
}
}
return anc[u][0];
}
struct segtree
{
int l;
int r;
int ct = 0;
segtree* left = NULL;
segtree* right = NULL;
void insert(int I, int V)
{
ct += V;
if(l != r)
{
int m = (l+r)/2;
if(I <= m)
{
if(left == NULL) left = new segtree{l, m, 0, NULL, NULL};
left->insert(I, V);
}
else
{
if(right == NULL) right = new segtree{m+1, r, 0, NULL, NULL};
right->insert(I, V);
}
}
}
int count_leq(int I)
{
if(I >= r) return ct;
else if(I < l) return 0;
else
{
int lv = (left != NULL ? left->count_leq(I) : 0);
int rv = (right != NULL ? right->count_leq(I) : 0);
return lv + rv;
}
}
};
struct mst
{
int l;
int r;
segtree v{0, mx, 0, NULL, NULL};
mst* left = NULL;
mst* right = NULL;
mst()
{
;
}
mst(int L, int R)
{
l = L;
r = R;
if(l == r) return;
int m = (l+r)/2;
left = new mst(l, m);
right = new mst(m+1, r);
}
void insert(int I, int J, int V)
{
v.insert(J, V);
if(l != r)
{
if(I <= (l+r)/2) left->insert(I, J, V);
else right->insert(I, J, V);
}
}
int getcount(int L, int R, int X)
{
if(R < l || r < L) return 0;
else if(L <= l && r <= R) return v.count_leq(X);
else return left->getcount(L, R, X) + right->getcount(L, R, X);
}
};
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> R >> C >> Q;
N = R * C;
for(int i = 0; i < N; i++) cin >> L[i];
for(int i = 0; i < N; i++) cin >> P[i];
for(int r = 0; r < R-1; r++)
for(int c = 0; c < C; c++)
add_edge(C*r + c, C*(r+1) + c);
for(int r = 0; r < R; r++)
for(int c = 0; c < C-1; c++)
add_edge(C*r + c, C*r + (c+1));
vpii ord;
for(int i = 0; i < N; i++)
ord.push_back({L[i], i});
sort(ord.begin(), ord.end());
disjoint_set DS;
for(int i = 0; i < N; i++)
reach_parent[i] = i;
int rt;
for(auto up: ord)
{
int u = up.second;
rt = u;
for(int v: edge[u])
{
if(L[v] >= L[u]) continue;
if(DS.connected(u, v)) continue;
int pu = DS.getpeak(u);
int pv = DS.getpeak(v);
reach_parent[pv] = pu;
reach_children[pu].push_back(pv);
DS.join(u, v);
}
}
for(int i = 0; i < N; i++)
anc[i][0] = reach_parent[i];
for(int e = 1; e <= lg; e++)
for(int i = 0; i < N; i++)
anc[i][e] = anc[ anc[i][e-1] ][e-1];
dfs(rt);
mst MST(1, N);
{
vi prv_same(1+N, 0); //indexed by dfs order
set<int> occ[1+mx];
for(int p = 1; p <= mx; p++)
{
occ[p].insert(0);
}
for(int i = 0; i < N; i++)
occ[P[i]].insert( ord_index[i] );
for(int p = 1; p <= mx; p++)
{
int prvval = 0;
for(int o : occ[p])
{
if(o == 0) continue;
prv_same[o] = prvval;
prvval = o;
}
}
for(int id = 1; id <= N; id++)
MST.insert(id, prv_same[id], +1);
}
for(int j = 0; j < Q; j++)
{
int T;
cin >> T;
if(T == 1)
{
int x, y, p;
cin >> x >> y >> p;
x--;
y--;
int z = C*y + x;
P[z] = p;
vi prv_same(1+N, 0); //indexed by dfs order
set<int> occ[1+mx];
for(int p = 1; p <= mx; p++)
{
occ[p].insert(0);
}
for(int i = 0; i < N; i++)
occ[P[i]].insert( ord_index[i] );
for(int p = 1; p <= mx; p++)
{
int prvval = 0;
for(int o : occ[p])
{
if(o == 0) continue;
prv_same[o] = prvval;
prvval = o;
}
}
MST = mst(1, N);
for(int id = 1; id <= N; id++)
MST.insert(id, prv_same[id], +1);
}
else
{
int x, y, l;
cin >> x >> y >> l;
x--;
y--;
set<int> res;
int z = C*y + x;
if(L[z] > l)
{
cout << 0 << '\n';
continue;
}
for(int e = lg; e >= 0; e--)
if(L[ anc[z][e] ] <= l)
z = anc[z][e];
int li = ord_index[z];
int ri = ord_index[z] + subtree[z] - 1;
cout << MST.getcount(li, ri, li-1) << '\n';
}
}
}
Compilation message
pokemonmaster.cpp: In function 'int main()':
pokemonmaster.cpp:340:5: warning: 'rt' may be used uninitialized in this function [-Wmaybe-uninitialized]
340 | dfs(rt);
| ~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
630 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
228 ms |
181784 KB |
Output is correct |
| 2 |
Runtime error |
617 ms |
524292 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
612 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
630 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
630 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
