oj.uz

Submission #926556

# Submission time Handle Problem Language Result Execution time Memory
926556 2024-02-13T09:31:53 Z pcc I want to be the very best too! (NOI17_pokemonmaster) C++17
100 / 100
 2735 ms 74440 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]){
		//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]);
      |                ~^~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 71820 KB Output is correct
2 Correct 140 ms 71876 KB Output is correct
3 Correct 154 ms 72324 KB Output is correct
4 Correct 143 ms 72448 KB Output is correct
5 Correct 149 ms 72272 KB Output is correct
6 Correct 138 ms 72364 KB Output is correct
7 Correct 193 ms 72396 KB Output is correct
8 Correct 141 ms 72448 KB Output is correct
9 Correct 137 ms 72396 KB Output is correct
10 Correct 178 ms 72352 KB Output is correct
11 Correct 141 ms 72372 KB Output is correct
12 Correct 147 ms 72468 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 70844 KB Output is correct
2 Correct 134 ms 70860 KB Output is correct
3 Correct 169 ms 70900 KB Output is correct
4 Correct 140 ms 71016 KB Output is correct
5 Correct 141 ms 71380 KB Output is correct
6 Correct 147 ms 70344 KB Output is correct
7 Correct 192 ms 69584 KB Output is correct
8 Correct 160 ms 69640 KB Output is correct
9 Correct 161 ms 69580 KB Output is correct
10 Correct 154 ms 69572 KB Output is correct
11 Correct 150 ms 69488 KB Output is correct
12 Correct 155 ms 69576 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 394 ms 70956 KB Output is correct
2 Correct 769 ms 73292 KB Output is correct
3 Correct 1060 ms 72944 KB Output is correct
4 Correct 1068 ms 73148 KB Output is correct
5 Correct 773 ms 73676 KB Output is correct
6 Correct 390 ms 72912 KB Output is correct
7 Correct 802 ms 71764 KB Output is correct
8 Correct 779 ms 71884 KB Output is correct
9 Correct 805 ms 71668 KB Output is correct
10 Correct 805 ms 71704 KB Output is correct
11 Correct 801 ms 71908 KB Output is correct
12 Correct 792 ms 71804 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 71820 KB Output is correct
2 Correct 140 ms 71876 KB Output is correct
3 Correct 154 ms 72324 KB Output is correct
4 Correct 143 ms 72448 KB Output is correct
5 Correct 149 ms 72272 KB Output is correct
6 Correct 138 ms 72364 KB Output is correct
7 Correct 193 ms 72396 KB Output is correct
8 Correct 141 ms 72448 KB Output is correct
9 Correct 137 ms 72396 KB Output is correct
10 Correct 178 ms 72352 KB Output is correct
11 Correct 141 ms 72372 KB Output is correct
12 Correct 147 ms 72468 KB Output is correct
13 Correct 358 ms 73940 KB Output is correct
14 Correct 1171 ms 73928 KB Output is correct
15 Correct 2242 ms 73964 KB Output is correct
16 Correct 1210 ms 73948 KB Output is correct
17 Correct 1204 ms 74332 KB Output is correct
18 Correct 414 ms 74440 KB Output is correct
19 Correct 824 ms 74024 KB Output is correct
20 Correct 1221 ms 74112 KB Output is correct
21 Correct 992 ms 74008 KB Output is correct
22 Correct 1766 ms 73992 KB Output is correct
23 Correct 1370 ms 74004 KB Output is correct
24 Correct 1381 ms 74432 KB Output is correct

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 71820 KB Output is correct
2 Correct 140 ms 71876 KB Output is correct
3 Correct 154 ms 72324 KB Output is correct
4 Correct 143 ms 72448 KB Output is correct
5 Correct 149 ms 72272 KB Output is correct
6 Correct 138 ms 72364 KB Output is correct
7 Correct 193 ms 72396 KB Output is correct
8 Correct 141 ms 72448 KB Output is correct
9 Correct 137 ms 72396 KB Output is correct
10 Correct 178 ms 72352 KB Output is correct
11 Correct 141 ms 72372 KB Output is correct
12 Correct 147 ms 72468 KB Output is correct
13 Correct 142 ms 70844 KB Output is correct
14 Correct 134 ms 70860 KB Output is correct
15 Correct 169 ms 70900 KB Output is correct
16 Correct 140 ms 71016 KB Output is correct
17 Correct 141 ms 71380 KB Output is correct
18 Correct 147 ms 70344 KB Output is correct
19 Correct 192 ms 69584 KB Output is correct
20 Correct 160 ms 69640 KB Output is correct
21 Correct 161 ms 69580 KB Output is correct
22 Correct 154 ms 69572 KB Output is correct
23 Correct 150 ms 69488 KB Output is correct
24 Correct 155 ms 69576 KB Output is correct
25 Correct 394 ms 70956 KB Output is correct
26 Correct 769 ms 73292 KB Output is correct
27 Correct 1060 ms 72944 KB Output is correct
28 Correct 1068 ms 73148 KB Output is correct
29 Correct 773 ms 73676 KB Output is correct
30 Correct 390 ms 72912 KB Output is correct
31 Correct 802 ms 71764 KB Output is correct
32 Correct 779 ms 71884 KB Output is correct
33 Correct 805 ms 71668 KB Output is correct
34 Correct 805 ms 71704 KB Output is correct
35 Correct 801 ms 71908 KB Output is correct
36 Correct 792 ms 71804 KB Output is correct
37 Correct 358 ms 73940 KB Output is correct
38 Correct 1171 ms 73928 KB Output is correct
39 Correct 2242 ms 73964 KB Output is correct
40 Correct 1210 ms 73948 KB Output is correct
41 Correct 1204 ms 74332 KB Output is correct
42 Correct 414 ms 74440 KB Output is correct
43 Correct 824 ms 74024 KB Output is correct
44 Correct 1221 ms 74112 KB Output is correct
45 Correct 992 ms 74008 KB Output is correct
46 Correct 1766 ms 73992 KB Output is correct
47 Correct 1370 ms 74004 KB Output is correct
48 Correct 1381 ms 74432 KB Output is correct
49 Correct 384 ms 73712 KB Output is correct
50 Correct 1356 ms 73576 KB Output is correct
51 Correct 2735 ms 73620 KB Output is correct
52 Correct 1284 ms 73480 KB Output is correct
53 Correct 1232 ms 74256 KB Output is correct
54 Correct 551 ms 73416 KB Output is correct
55 Correct 830 ms 71992 KB Output is correct
56 Correct 1282 ms 72456 KB Output is correct
57 Correct 843 ms 72072 KB Output is correct
58 Correct 1648 ms 72344 KB Output is correct
59 Correct 1362 ms 72244 KB Output is correct
60 Correct 1628 ms 72268 KB Output is correct