oj.uz

답안 #1111308

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1111308 2024-11-12T03:38:29 Z thieunguyenhuy 모자이크 (IOI24_mosaic) C++17
12 / 100
 1000 ms 108616 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));
		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) {
			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(n, 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;
	}
}

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();
}

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), B(q), L(q), R(q);
    
    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

Compilation message

mosaic.cpp: In function 'std::vector<long long int> mosaic(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
mosaic.cpp:132:1: warning: control reaches end of non-void function [-Wreturn-type]
  132 | }
      | ^

Subtask #0
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 612 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 2 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 444 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 612 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 2 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 444 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 55 ms 880 KB Output is correct
12 Correct 56 ms 888 KB Output is correct
13 Correct 61 ms 840 KB Output is correct
14 Correct 56 ms 844 KB Output is correct
15 Correct 12 ms 336 KB Output is correct
16 Correct 13 ms 488 KB Output is correct
17 Correct 13 ms 336 KB Output is correct

Subtask #3
0.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 86 ms 17112 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 612 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 2 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 444 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 55 ms 880 KB Output is correct
12 Correct 56 ms 888 KB Output is correct
13 Correct 61 ms 840 KB Output is correct
14 Correct 56 ms 844 KB Output is correct
15 Correct 12 ms 336 KB Output is correct
16 Correct 13 ms 488 KB Output is correct
17 Correct 13 ms 336 KB Output is correct
18 Execution timed out 1069 ms 108616 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 12360 KB Output is correct
2 Incorrect 74 ms 17364 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 77 ms 16668 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 86 ms 17112 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 612 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 2 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 444 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 55 ms 880 KB Output is correct
13 Correct 56 ms 888 KB Output is correct
14 Correct 61 ms 840 KB Output is correct
15 Correct 56 ms 844 KB Output is correct
16 Correct 12 ms 336 KB Output is correct
17 Correct 13 ms 488 KB Output is correct
18 Correct 13 ms 336 KB Output is correct
19 Incorrect 86 ms 17112 KB Output isn't correct
20 Halted 0 ms 0 KB -