#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>
#define ordered_set(T) tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>
const int mxn = 1e5+10;
ordered_set(pii) bit[mxn];
ordered_set(int) cols[mxn];
pii eul[mxn];
vector<int> paths[mxn];
int par[mxn][20];
int dep[mxn];
int str[mxn],kind[mxn],act[mxn];
int R,C,Q,N;
int cnt;
int dsu[mxn],sz[mxn];
pii head[mxn];
pii dir[] = {{0,1},{0,-1},{1,0},{-1,0}};
vector<pair<int,pii>> v;
vector<int> dfn;
int rp[mxn];
int root(int k){
return k == dsu[k]?k:dsu[k] = root(dsu[k]);
}
void onion(int a,int b){
a = root(a),b = root(b);
if(a == b)return;
if(sz[a]<sz[b])swap(a,b);
dsu[b] = a;
sz[a] += sz[b];
head[a] = max(head[a],head[b]);
return;
}
void dfs(int now){
for(int i = 1;i<20;i++)par[now][i] = par[par[now][i-1]][i-1];
dfn.push_back(now);
eul[now].fs = dfn.size()-1;
for(auto nxt:paths[now]){
cout<<now<<' '<<nxt<<endl;
par[nxt][0] = now;
dep[nxt] = dep[now]+1;
dfs(nxt);
}
eul[now].sc = dfn.size()-1;
return;
}
void add(int p,int v){
p++;
for(;p<mxn;p+=p&-p)bit[p].insert({v,++cnt});
}
void del(int p,int v){
p++;
for(;p<mxn;p+=p&-p)bit[p].erase(bit[p].lower_bound({v,-1}));
}
int getcnt(int p,int lim){
int re = 0;
p++;
for(;p>0;p-= p&-p){
int cnt = bit[p].size()-bit[p].order_of_key({lim+1,-1});
re += cnt;
}
return re;
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>R>>C>>Q;
N = R*C;
for(int i = 0;i<R;i++)for(int j = 0;j<C;j++)cin>>str[i*C+j],v.push_back({str[i*C+j],{i,j}});
for(int i = 0;i<R;i++)for(int j = 0;j<C;j++)cin>>kind[i*C+j];
sort(v.begin(),v.end());
for(int i = 0;i<R;i++){
for(int j = 0;j<C;j++){
dsu[i*C+j] = i*C+j;
head[i*C+j] = {str[i*C+j],i*C+j};
sz[i*C+j] = 1;
}
}
int rt = v.back().sc.fs*C+v.back().sc.sc;
for(auto &i:v){
pii pos = i.sc;
act[pos.fs*C+pos.sc] = true;
for(auto &d:dir){
pii nxt = {pos.fs+d.fs,pos.sc+d.sc};
if(nxt.fs>=R||nxt.sc>=C||nxt.fs<0||nxt.sc<0||!act[nxt.fs*C+nxt.sc])continue;
if(root(pos.fs*C+pos.sc) == root(nxt.fs*C+nxt.sc))continue;
int a = head[root(pos.fs*C+pos.sc)].sc,b = head[root(nxt.fs*C+nxt.sc)].sc;
paths[a].push_back(b);
onion(pos.fs*C+pos.sc,nxt.fs*C+nxt.sc);
}
}
par[rt][0] = rt;
dfs(rt);
for(int i = 0;i<mxn;i++)cols[i].insert(mxn);
for(int i = dfn.size()-1;i>=0;i--){
int now = dfn[i];
int c = kind[now];
rp[i] = *cols[c].begin();
cols[c].insert(i);
}
for(int i = 0;i<dfn.size();i++)add(i,rp[i]);
while(Q--){
int t,r,c,val;
cin>>t>>c>>r>>val;
c--,r--;
if(t == 1){
int now = r*C+c;
int eid = eul[now].fs;
del(eid,rp[eid]);
cols[kind[now]].erase(eid);
auto it = cols[kind[now]].lower_bound(eid);
if(it != cols[kind[now]].begin()){
it--;
del(*it,eid);
rp[*it] = *next(it);
add(*it,*next(it));
}
kind[now] = val;
it = cols[kind[now]].lower_bound(eid);
rp[eid] = *it;
add(eid,rp[eid]);
if(it != cols[kind[now]].begin()){
it--;
del(*it,*next(it));
rp[*it] = eid;
add(*it,eid);
}
cols[kind[now]].insert(eid);
}
else{
int now = r*C+c;
if(str[now]>val){
cout<<"0\n";
continue;
}
for(int i = 19;i>=0;i--){
int p = par[now][i];
if(str[p]<=val)now = p;
}
cout<<getcnt(eul[now].sc,eul[now].sc)-getcnt(eul[now].fs-1,eul[now].sc)<<'\n';
}
}
return 0;
}
Compilation message
pokemonmaster.cpp: In function 'int main()':
pokemonmaster.cpp:114:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
114 | for(int i = 0;i<dfn.size();i++)add(i,rp[i]);
| ~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
193 ms |
74812 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
247 ms |
73280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
436 ms |
73628 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
193 ms |
74812 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
193 ms |
74812 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
