oj.uz

Submission #926547

# Submission time Handle Problem Language Result Execution time Memory
926547 2024-02-13T09:14:58 Z pcc I want to be the very best too! (NOI17_pokemonmaster) C++17
16 / 100
 378 ms 73500 KB 
#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]){
		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,eid);
				rp[*it] = *next(it);
				add(*it,*next(it));
			}
			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:113:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |  for(int i = 0;i<dfn.size();i++)add(i,rp[i]);
      |                ~^~~~~~~~~~~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 72408 KB Output is correct
2 Incorrect 141 ms 72360 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 71552 KB Output is correct
2 Correct 138 ms 71712 KB Output is correct
3 Correct 143 ms 72080 KB Output is correct
4 Correct 148 ms 71816 KB Output is correct
5 Correct 140 ms 72028 KB Output is correct
6 Correct 157 ms 70908 KB Output is correct
7 Correct 198 ms 70376 KB Output is correct
8 Correct 148 ms 70340 KB Output is correct
9 Correct 140 ms 70424 KB Output is correct
10 Correct 163 ms 70336 KB Output is correct
11 Correct 153 ms 70200 KB Output is correct
12 Correct 166 ms 70256 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 378 ms 73500 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 72408 KB Output is correct
2 Incorrect 141 ms 72360 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 72408 KB Output is correct
2 Incorrect 141 ms 72360 KB Output isn't correct
3 Halted 0 ms 0 KB -