Submission #1177475

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177475		Kaztaev_Alisher	Mosaic (IOI24_mosaic)	C++20	53 / 100	368 ms	194172 KiB

mosaic

#include <bits/stdc++.h>

#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
#define all(a) a.begin() , a.end()
#define F first
#define S second

using namespace std;
using ll = long long;

const ll N = 2e5+5 , inf = 2e9 + 7;
const ll INF = 1e18 ,   mod = 1e9+7;

unordered_map<int,int> dp[N] , pr[N];
vector<int> vec;
int get(int x){
	int l = 0 , r = vec.size()-1 , res = -1;
	while(l <= r){
		int md = (l+r) >> 1;
		if(vec[md] <= x){
			res = md;
			l = md+1;
		} else {
			r = md-1;
		}
	}
	return res;
}
vector<long long> mosaic(vector<int> X, vector<int> Y, vector<int> T, vector<int> B, vector<int> L, vector<int> R) {
	int n = X.size();
	for(int i = 1; i <= n; i++){
		dp[1][i] = X[i-1];
		dp[i][1] = Y[i-1];
	}
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			if(i == 1 || j == 1) continue;
			if(i > 3 && j > 3) break;
			if(dp[i-1][j] == 0 && dp[i][j-1] == 0) dp[i][j] = 1;
			else dp[i][j] = 0;
			// cout << dp[i][j] <<" ";
		}
		// cout << "\n";
	}
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			if(i > 3 && j > 3) break;
			pr[i][j] = dp[i][j] + pr[i][j-1] + pr[i-1][j] - pr[i-1][j-1];
		}
	}
	set<int> st;
	for(int j = 3 , i = 3; j <= n; j++){
		if(dp[i][j] == 1){
			st.insert(i-j);
		}
	}
	for(int i = 3 , j = 3; i <= n; i++){
		if(dp[i][j] == 1){
			st.insert(i-j);
		}
	}
	for(auto it : st) {
		vec.push_back(it);
		// cout << it <<" ";
	}
	// cout << "\n";
	int q = (int)T.size();
	vector<long long> C(q, 0);
	for(int i = 0; i < q; i++){
		B[i]++;
		R[i]++;
		if(R[i] <= 3 || B[i] <= 3){
			// C[i] = dp[B[i]][R[i]];
			C[i] = pr[B[i]][R[i]]-pr[B[i]][L[i]]-pr[T[i]][R[i]]+pr[T[i]][L[i]];
		} else {
			L[i]++;
			ll ans = 0;
			while(L[i] <= 3){
				ans += dp[B[i]][L[i]];
				L[i]++;
			}
			C[i] = get(B[i]-L[i])-get(B[i]-(R[i]+1)) + ans; 
		}
	}
	return C;
}

// int main() {
  // int N;
  // assert(1 == scanf("%d", &N));
  // std::vector<int> X(N), Y(N);
  // for (int i = 0; i < N; i++)
    // assert(1 == scanf("%d", &X[i]));
  // for (int i = 0; i < N; i++)
    // assert(1 == scanf("%d", &Y[i]));
  // int Q;
  // assert(1 == scanf("%d", &Q));
  // std::vector<int> T(Q), B(Q), L(Q), R(Q);
  // for (int k = 0; k < Q; k++)
    // assert(4 == scanf("%d%d%d%d", &T[k], &B[k], &L[k], &R[k]));
  // fclose(stdin);
// 
  // std::vector<long long> C = mosaic(X, Y, T, B, L, R);
// 
  // int S = (int)C.size();
  // for (int k = 0; k < S; k++)
    // printf("%lld\n", C[k]);
  // fclose(stdout);
// 
  // return 0;
// }

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 0 / 7
• Subtask 3: 7 / 7
• Subtask 4: 0 / 10
• Subtask 5: 0 / 8
• Subtask 6: 22 / 22
• Subtask 7: 19 / 19
• Subtask 8: 0 / 22