#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())
#define dbg if(debugging)cerr
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);
}
bool debugging = 1;
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);
// 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;
}
}
};
segtree* attach(segtree* st, int I, int V, int lv, int rv)
{
segtree* ln = new segtree{I, I, V, NULL, NULL};
segtree* rn = st;
if(ln->l > rn->l) swap(ln, rn);
while(1)
{
if((lv+rv)/2 >= rn->r)
rv = (lv+rv)/2;
else if((lv+rv)/2+1 <= ln->l)
lv = (lv+rv)/2+1;
else break;
}
return new segtree{lv, rv, ln->ct + rn->ct, ln, rn};
}
void segtree::insert(int I, int V)
{
ct += V;
if(l != r)
{
int m = (l+r)/2;
if(I <= m)
{
if(left == NULL) left = new segtree{I, I, V, NULL, NULL};
else if(left->l <= I && I <= left->r) left->insert(I, V);
else left = attach(left, I, V, l, r);
}
else
{
if(right == NULL) left = new segtree{I, I, V, NULL, NULL};
else if(right->l <= I && I <= right->r) right->insert(I, V);
else right = attach(right, I, V, l, r);
}
}
}
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)
{
if(l == 1 && r == N) cerr << I << ' ' << J << " : " << V << '\n';
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);
vi prv_same(1+N, 0);//indexed by dfs order
mst MST(1, N);
// for(int i = 0; i < N; i++) cerr << ord_index[i] << ' ';
// cerr << "\n";
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;
// cerr << "prv same " << o << " = " << prvval << '\n';
prvval = o;
}
}
for(int id = 1; id <= N; id++)
MST.insert(id, prv_same[id], +1);
// for(int i = 0; i < N; i++) cerr << reach_parent[i] << ' ' << ord_index[i] << '\n';
cerr << "answering queries\n";
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;
int oldp = P[z];
int newp = p;
P[z] = p;
// cerr << oldp << ' ' << newp << '\n';
if(oldp == newp)
{
cerr << "waste\n";
continue;
}
// cerr << "z = " << z << '\n';
auto oldfind = occ[oldp].find(ord_index[z]);
int of = *oldfind;
auto oldfind_prev = oldfind;
oldfind_prev--;
int ofp = *oldfind_prev;
auto oldfind_next = oldfind;
oldfind_next++;
// cerr << "ofp = "
// cerr << "part1\n";
MST.insert(of, ofp, -1);
if(oldfind_next != occ[oldp].end())
{
int ofn = *oldfind_next;
MST.insert(ofn, of, -1);
MST.insert(ofn, ofp, +1);
}
auto newfind = occ[newp].lower_bound(ord_index[z]);
int nfn = -1;
if(newfind != occ[newp].end())
nfn = *newfind;
newfind--;
int nfp = *newfind;
// cerr << "part2\n";
MST.insert(ord_index[z], nfp, +1);
if(nfn != -1)
{
MST.insert(nfn, nfp, -1);
MST.insert(nfn, ord_index[z], +1);
}
occ[oldp].erase(ord_index[z]);
occ[newp].insert(ord_index[z]);
}
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;
}
// cerr << "z1 = " << z << '\n';
for(int e = lg; e >= 0; e--)
if(L[ anc[z][e] ] <= l)
z = anc[z][e];
// cerr << "z2 = " << z << '\n';
int li = ord_index[z];
int ri = ord_index[z] + subtree[z] - 1;
// cerr << li << ' ' << ri << '\n';
cout << MST.getcount(li, ri, li-1) << '\n';
}
}
}
Compilation message
pokemonmaster.cpp: In function 'int main()':
pokemonmaster.cpp:393:5: warning: 'rt' may be used uninitialized in this function [-Wmaybe-uninitialized]
393 | dfs(rt);
| ~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
479 ms |
87556 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
464 ms |
86792 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
918 ms |
96884 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
479 ms |
87556 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
479 ms |
87556 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
