| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1206235 | loom | I want to be the very best too! (NOI17_pokemonmaster) | C++20 | 0 ms | 0 KiB |
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include<bits/stdc++.h>
using namespace std;
#define nl '\n'
using namespace __gnu_pbds;
template<class T> using indexed_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int N = 5e4+5;
set<int> st[N];
vector<int> g[N], et;
indexed_set<int> seg[4*N];
int mx[N], pr[N], sz[N], pt[N], lt[N], in[N], out[N], lst[N], up[N][16];
int find(int x){
return x == pr[x] ? x : (pr[x] = find(pr[x]));
}
void unite(int x, int y){
x = find(x);
y = find(y);
if(x == y) return;
g[mx[x]].push_back(mx[y]);
if(sz[x] < sz[y]) swap(x, y);
mx[x] = max(mx[x], mx[y]);
pr[y] = x;
sz[x] += sz[y];
}
void dfs(int v){
in[v] = et.size();
et.push_back(v);
for(int ch : g[v]){
up[ch][0] = v;
dfs(ch);
}
out[v] = et.size()-1;
}
void build(int l, int r, int p){
if(l == r){
seg[p].insert({lst[l], l});
return;
}
int m = (l+r)/2;
build(l, m, p*2);
build(m+1, r, p*2+1);
for(int x : seg[p*2]) seg[p].insert(x);
for(int x : seg[p*2+1]) seg[p].insert(x);
}
int upd(int l, int r, int p, int q, int v){
if(l == r){
int x = *seg[p].begin();
seg[p].clear();
seg[p].insert(v);
return x;
}
int m = (l+r)/2, x;
if(q <= m) x = upd(l, m, p*2, q, v);
else x = upd(m+1, r, p*2+1, q, v);
seg[p].erase(seg[p].find_by_order(seg[p].order_of_key(x)));
seg[p].insert(v);
return x;
}
void seg_upd(int q, int v){
upd(0, N-1, 1, q, v);
}
int qry(int l, int r, int p, int ql, int qr){
if(r < ql or qr < l) return 0;
if(ql <= l and r <= qr) return seg[p].order_of_key(ql);
int m = (l+r)/2;
return qry(l, m, p*2, ql, qr) + qry(m+1, r, p*2+1, ql, qr);
}
int qry(int ql, int qr){
return qry(0, N-1, 1, ql, qr);
}
void upd(int i, int v){
int x = pt[et[i]];
auto &u = st[x];
u.erase(i);
auto it = u.lower_bound(i);
if(it != u.end()) seg_upd(*it, *prev(it));
auto &w = st[v];
it = w.lower_bound(i);
if(it != w.end()) seg_upd(*it, i);
w.insert(i);
seg_upd(i, *----it);
}
inline void solve(){
int n, m, q;
cin>>n>>m>>q;
int tot = n*m;
int l[n+1][m+1];
vector<tuple<int,int,int>> v;
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
cin>>l[i][j];
v.push_back({l[i][j], i, j});
}
}
sort(v.begin(), v.end());
int p[n+1][m+1];
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
cin>>p[i][j];
}
}
iota(mx, mx+N, 0);
iota(pr, pr+N, 0);
fill(sz, sz+N, 1);
int ix[n+1][m+1];
for(int i=0; i<tot; i++){
auto [x, a, b] = v[i];
ix[a][b] = i;
pt[i] = p[a][b];
lt[i] = l[a][b];
if(a+1 <= n and l[a+1][b] < x) unite(i, ix[a+1][b]);
if(a-1 > 0 and l[a-1][b] < x) unite(i, ix[a-1][b]);
if(b+1 <= m and l[a][b+1] < x) unite(i, ix[a][b+1]);
if(b-1 > 0 and l[a][b-1] < x) unite(i, ix[a][b-1]);
}
dfs(tot-1);
up[tot-1][0] = tot-1;
for(int j=1; j<16; j++){
for(int i=0; i<tot; i++){
up[i][j] = up[up[i][j-1]][j-1];
}
}
for(int i=1; i<N; i++) st[i].insert(-1);
for(int i=0; i<tot; i++){
int x = pt[et[i]];
lst[i] = *st[x].rbegin();
st[x].insert(i);
}
build(0, N-1, 1);
while(q--){
int w, x, y, v;
cin>>w>>x>>y>>v;
swap(x, y);
int pos = ix[x][y];
if(w == 1){
upd(in[pos], v);
pt[pos] = v;
continue;
}
if(lt[pos] > v){
cout<<0<<nl;
continue;
}
for(int i=15; i>=0; i--){
if(lt[up[pos][i]] <= v) pos = up[pos][i];
}
cout<<qry(in[pos], out[pos])<<nl;
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(NULL);cout.tie(NULL);
int t = 1;
//cin>>t;
while(t--) solve();
return 0;
}