Submission #587495

#	Time	Username	Problem	Language	Result	Execution time	Memory
587495		NekoRolly	I want to be the very best too! (NOI17_pokemonmaster)	C++17	51 / 100	91 ms	10316 KiB

pokemonmaster

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e4+4;

struct Bit{
	int n,t[N];

	void up(int i,int val){
		for (; i<=n; i+=i&-i) t[i] += val;
	}

	int que(int i){ int ans = 0;
		for (; i>0; i-=i&-i) ans += t[i];
		return ans;
	}
} d1;

int n,m,q;
vector<vector<int>> level,poke,vis;
bool use[N];
set<int> d2[N];

bool valid(int a,int b,int x){
	return 0 < a && a <= n && 0 < b && b <= m && !vis[a][b] && level[a][b] <= x;
}

void dfs(int a,int b,int x){ use[poke[a][b]] = vis[a][b] = 1;
	if (valid(a-1, b, x)) dfs(a-1, b, x);
	if (valid(a+1, b, x)) dfs(a+1, b, x);
	if (valid(a, b-1, x)) dfs(a, b-1, x);
	if (valid(a, b+1, x)) dfs(a, b+1, x);
}

void up(int x,int val,int f){
	if (d2[x].size()) d1.up(*d2[x].begin(), -1);
	if (f == 1) d2[x].insert(val);
	if (f == -1) d2[x].erase(val);
	if (d2[x].size()) d1.up(*d2[x].begin(), 1);
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	cin >> n >> m >> q;
	level.resize(n+1, vector<int> (m+1));
	poke.resize(n+1, vector<int> (m+1));
	vis.resize(n+1, vector<int> (m+1));

	for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) cin >> level[i][j];
	for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) cin >> poke[i][j];

	if (q <= 10){
		for (int t,a,b,x,ans; q; q--){ cin >> t >> b >> a >> x;
			if (t == 1) poke[a][b] = x;
			if (t == 2){ ans = 0;
				for (int i=1; i<N; i++) use[i] = 0;
				for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) vis[i][j] = 0;
				if (level[a][b] <= x) dfs(a, b, x);
				for (int i=1; i<N; i++) ans += use[i], use[i] = 0;
				cout << ans << "\n";
			}
		}
	}
	else if (n == 1){ d1.n = m;
		for (int i=1; i<=m; i++) d2[poke[1][i]].insert(i);
		for (int i=1; i<N; i++) if (d2[i].size()) d1.up(*d2[i].begin(), 1);

		for (int t,a,b,x,ans; q; q--){ cin >> t >> b >> a >> x;
			if (t == 1){ up(poke[a][b], b, -1);
				up(poke[a][b] = x, b, 1);
			}
			if (t == 2) cout << (b <= x ? d1.que(min(x, m)) : 0) << "\n";
		}
	}

    return 0;
}

Compilation message (stderr)

pokemonmaster.cpp: In function 'void dfs(int, int, int)':
pokemonmaster.cpp:28:58: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   28 | void dfs(int a,int b,int x){ use[poke[a][b]] = vis[a][b] = 1;
pokemonmaster.cpp: In function 'int main()':
pokemonmaster.cpp:69:20: warning: unused variable 'ans' [-Wunused-variable]
   69 |   for (int t,a,b,x,ans; q; q--){ cin >> t >> b >> a >> x;
      |                    ^~~

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