oj.uz

Submission #1111384

# Submission time Handle Problem Language Result Execution time Memory
1111384 2024-11-12T07:58:54 Z thieunguyenhuy Mosaic (IOI24_mosaic) C++17
37 / 100
 1000 ms 305480 KB 
#include <bits/stdc++.h>
using namespace std;

#define popcount(n) (__builtin_popcountll((n)))
#define clz(n) (__builtin_clzll((n)))
#define ctz(n) (__builtin_ctzll((n)))
#define lg(n) (63 - __builtin_clzll((n)))
#define BIT(n, i) (((n) >> (i)) & 1ll)
#define MASK(i) (1ll << (i))
#define FLIP(n, i) ((n) ^ (1ll << (i)))
#define ON(n, i) ((n) | MASK(i))
#define OFF(n, i) ((n) & ~MASK(i))

#define Int __int128
#define fi first
#define se second

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef pair<long long, int> pli;
typedef pair<int, long long> pil;
typedef vector<pair<int, int>> vii;
typedef vector<pair<long long, long long>> vll;
typedef vector<pair<long long, int>> vli;
typedef vector<pair<int, long long>> vil;

template <class T1, class T2>
bool maximize(T1 &x, T2 y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}
template <class T1, class T2>
bool minimize(T1 &x, T2 y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}

template <class T>
void remove_duplicate(vector<T> &ve) {
    sort (ve.begin(), ve.end());
    ve.resize(unique(ve.begin(), ve.end()) - ve.begin());
}

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
template <class T> T random(T l, T r) {
    return uniform_int_distribution<T>(l, r)(rng);
}
template <class T> T random(T r) {
    return rng() % r;
}

const int N = 1e6 + 5;
const int MOD = 1e9 + 7;
const int inf = 1e9;
const long long INF = 1e18;

int n, q;
vector<int> X, Y, T, B, L, R;

namespace sub124 {
	vector<ll> solve() {
		vector<vector<int>> c(n, vector<int>(n, 0));
		for (int i = 0; i < n; ++i) c[0][i] = X[i];
		for (int i = 0; i < n; ++i) c[i][0] = Y[i];

		// for (int i = 1; i < n; ++i) for (int j = 1; j < n; ++j) {
		// 	if (i > 5 && j > 5) break;
		// 	if (!c[i - 1][j] && !c[i][j - 1]) {
		// 		for (int k = 0; i + k < n && j + k < n; ++k)
		// 			c[i + k][j + k] = 1;
		// 	}
		// }

		for (int i = 1; i < n; ++i) for (int j = 1; j < n; ++j) {
			c[i][j] = !(c[i - 1][j] | c[i][j - 1]);
		}

		// for (int i = 0; i < n; ++i) {
		// 	for (int j = 0; j < n; ++j) cerr << c[i][j];
		// 	cerr << '\n';
		// }

		vector<vector<ll>> pref(n, vector<ll>(n, 0));
		for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) {
			pref[i][j] = c[i][j];
			if (i > 0) pref[i][j] += pref[i - 1][j];
			if (j > 0) pref[i][j] += pref[i][j - 1];
			if (i > 0 && j > 0) pref[i][j] -= pref[i - 1][j - 1];
		}

		auto get = [&](int x, int y, int u, int v) {
			ll ans = pref[u][v];
			if (x > 0) ans -= pref[x - 1][v];
			if (y > 0) ans -= pref[u][y - 1];
			if (x > 0 && y > 0) ans += pref[x - 1][y - 1];
			return ans;
		};

		vector<ll> ans(q);
		for (int i = 0; i < q; ++i) {
			ans[i] = get(T[i], L[i], B[i], R[i]);
		}

		return ans;
	}
}

namespace sub3 {
	bool check() {
		for (int i = 0; i < q; ++i) if (T[i] != 0 || B[i] != 0) {
			return false;
		}
		return true;
	}

	vector<ll> solve() {
		vector<int> pref(n, 0); vector<ll> ans(q, 0); pref[0] = X[0];
		for (int i = 1; i < n; ++i) pref[i] = pref[i - 1] + X[i];
		for (int i = 0; i < q; ++i) {
			ans[i] = pref[R[i]] - (L[i] == 0 ? 0 : pref[L[i] - 1]);
		}
		return ans;
	}
}

namespace sub5 {
	bool check() {
		for (int i = 0; i < n; ++i) if (X[i] != 0 || Y[i] != 0) {
			return false;
		}
		return true;
	}

	vector<ll> solve() {
		vector<ll> ans(q, 0);

		auto countEven = [&](int l, int r) {
			return (r / 2) - ((l - 1) / 2);
		};

		for (int i = 0; i < q; ++i) {
			maximize(T[i], 1), maximize(L[i], 1);
			int evenX = countEven(T[i], B[i]), oddX = (B[i] - T[i] + 1) - evenX,
				evenY = countEven(L[i], R[i]), oddY = (R[i] - L[i] + 1) - evenY;
			ans[i] = 0ll + 1ll * evenX * evenY + 1ll * oddX * oddY;
		}
		return ans;
	}
}

namespace sub678 {
	const int MAGIC = 6;

	int encode(int x, int y) {
		if (x < MAGIC) return x * n + y;
		return MAGIC * n + (x - MAGIC) * MAGIC + y;
	}

	vector<ll> solve() {
		int sz = 2 * MAGIC * n - MAGIC * MAGIC;
		vector<int> c(sz, 0);
		for (int i = 0; i < n; ++i) {
			c[encode(0, i)] = X[i];
			c[encode(i, 0)] = Y[i];
		}

		vector<int> diag(2 * n + 1, -1);
		for (int i = 1; i < MAGIC; ++i) for (int j = 1; j < n; ++j) {
			c[encode(i, j)] = !(c[encode(i - 1, j)] | c[encode(i, j - 1)]);
			if (c[encode(i, j)] && diag[j - i + n] == -1) diag[j - i + n] = i;
		}

		for (int i = MAGIC; i < n; ++i) for (int j = 1; j < MAGIC; ++j) {
			c[encode(i, j)] = !(c[encode(i - 1, j)] | c[encode(i, j - 1)]);
			if (c[encode(i, j)] && diag[j - i + n] == -1) diag[j - i + n] = i;
		}

		vector<ll> ans(q, 0);
		for (int i = 0; i < q; ++i) {
			for (int k = 0; k <= n; ++k) {
				int minX = max(diag[k + n], T[i]), minY = max(k + diag[k + n] - n, L[i]);
				ans[i] += min(B[i] - minX + 1, R[i] - minY + 1);
			}
		}

		return ans;
	}
}

vector<ll> mosaic(vector<int> _X, vector<int> _Y, vector<int> _T, vector<int> _B, vector<int> _L, vector<int> _R) {
	X = _X, Y = _Y, T = _T, B = _B, L = _L, R = _R;
	n = X.size(), q = T.size();
	if (n <= 5000) return sub124::solve();
	if (sub3::check()) return sub3::solve();
	if (sub5::check()) return sub5::solve();
	return sub678::solve();
}

void get(vector<int> &container) {
	for (auto &x : container) cin >> x;
}

#ifdef hwe
signed main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    int n, q; cin >> n >> q;

    vector<int> X(n, 0), Y(n, 0), T(q, 0), B(q, 0), L(q), R(q);
    
    get(X), get(Y);
    get(T), get(B);
    get(L), get(R);

   	vector<ll> ans = mosaic(X, Y, T, B, L, R);
   	for (auto &x : ans) cerr << x << ' ';
   	cerr << '\n';

    cerr << '\n'; return 0;
}
#endif

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 504 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 504 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 848 KB Output is correct
12 Correct 2 ms 848 KB Output is correct
13 Correct 1 ms 848 KB Output is correct
14 Correct 2 ms 848 KB Output is correct
15 Correct 1 ms 560 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 1 ms 400 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 16924 KB Output is correct
2 Correct 80 ms 16720 KB Output is correct
3 Correct 88 ms 16672 KB Output is correct
4 Correct 77 ms 16712 KB Output is correct
5 Correct 68 ms 14084 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 504 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 848 KB Output is correct
12 Correct 2 ms 848 KB Output is correct
13 Correct 1 ms 848 KB Output is correct
14 Correct 2 ms 848 KB Output is correct
15 Correct 1 ms 560 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 1 ms 400 KB Output is correct
18 Correct 502 ms 305364 KB Output is correct
19 Correct 355 ms 305480 KB Output is correct
20 Correct 372 ms 305480 KB Output is correct
21 Correct 344 ms 305416 KB Output is correct
22 Correct 363 ms 305400 KB Output is correct
23 Correct 125 ms 57884 KB Output is correct
24 Correct 115 ms 56904 KB Output is correct
25 Correct 116 ms 57096 KB Output is correct

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 11336 KB Output is correct
2 Correct 92 ms 15944 KB Output is correct
3 Correct 87 ms 15960 KB Output is correct
4 Correct 86 ms 18504 KB Output is correct
5 Correct 92 ms 17332 KB Output is correct
6 Correct 91 ms 17884 KB Output is correct
7 Correct 91 ms 16456 KB Output is correct
8 Correct 81 ms 15944 KB Output is correct
9 Correct 76 ms 14020 KB Output is correct
10 Correct 82 ms 15736 KB Output is correct
11 Correct 100 ms 16288 KB Output is correct

Subtask #6
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1053 ms 26952 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 16924 KB Output is correct
2 Correct 80 ms 16720 KB Output is correct
3 Correct 88 ms 16672 KB Output is correct
4 Correct 77 ms 16712 KB Output is correct
5 Correct 68 ms 14084 KB Output is correct
6 Execution timed out 1053 ms 26952 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #8
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 504 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 848 KB Output is correct
13 Correct 2 ms 848 KB Output is correct
14 Correct 1 ms 848 KB Output is correct
15 Correct 2 ms 848 KB Output is correct
16 Correct 1 ms 560 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 1 ms 400 KB Output is correct
19 Correct 80 ms 16924 KB Output is correct
20 Correct 80 ms 16720 KB Output is correct
21 Correct 88 ms 16672 KB Output is correct
22 Correct 77 ms 16712 KB Output is correct
23 Correct 68 ms 14084 KB Output is correct
24 Correct 502 ms 305364 KB Output is correct
25 Correct 355 ms 305480 KB Output is correct
26 Correct 372 ms 305480 KB Output is correct
27 Correct 344 ms 305416 KB Output is correct
28 Correct 363 ms 305400 KB Output is correct
29 Correct 125 ms 57884 KB Output is correct
30 Correct 115 ms 56904 KB Output is correct
31 Correct 116 ms 57096 KB Output is correct
32 Correct 56 ms 11336 KB Output is correct
33 Correct 92 ms 15944 KB Output is correct
34 Correct 87 ms 15960 KB Output is correct
35 Correct 86 ms 18504 KB Output is correct
36 Correct 92 ms 17332 KB Output is correct
37 Correct 91 ms 17884 KB Output is correct
38 Correct 91 ms 16456 KB Output is correct
39 Correct 81 ms 15944 KB Output is correct
40 Correct 76 ms 14020 KB Output is correct
41 Correct 82 ms 15736 KB Output is correct
42 Correct 100 ms 16288 KB Output is correct
43 Execution timed out 1053 ms 26952 KB Time limit exceeded
44 Halted 0 ms 0 KB -