Submission #926556

#	Time	Username	Problem	Language	Result	Execution time	Memory
926556		pcc	I want to be the very best too! (NOI17_pokemonmaster)	C++17	100 / 100	2735 ms	74440 KiB

pokemonmaster

#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 (stderr)

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]);
      |                ~^~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 16 / 16
• Subtask 3: 20 / 20
• Subtask 4: 24 / 24
• Subtask 5: 29 / 29