oj.uz

Submission #1111546

# Submission time Handle Problem Language Result Execution time Memory
1111546 2024-11-12T09:26:06 Z thieunguyenhuy Mosaic (IOI24_mosaic) C++17
27 / 100
 1000 ms 28960 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), row(n, 0), col(n, 0);
        for (int i = 0; i < n; ++i) {
            c[encode(0, i)] = X[i], row[i] = (i == 0 ? 0 : row[i - 1]) + X[i];
            c[encode(i, 0)] = Y[i], col[i] = (i == 0 ? 0 : col[i - 1]) + 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 k = -n; k <= n; ++k) {
            cerr << diag[k + n] << ' ' << k << '\n';
        }

        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) {
            if (T[i] == 0) ans[i] += row[R[i]] - (L[i] == 0 ? 0 : row[L[i] - 1]);
            if (L[i] == 0) ans[i] += col[B[i]] - (T[i] == 0 ? 0 : col[T[i] - 1]);
            if (T[i] == 0 && L[i] == 0) ans[i] -= c[encode(0, 0)];
            for (int k = -n; k <= n; ++k) if (diag[k + n] != -1) {
                int minX = max(diag[k + n], max(T[i], L[i] - k)), minY = k + minX;
                int contrib = min(max(0, B[i] - minX + 1), max(0, R[i] - minY + 1));
                // cerr << k << ' ' << minX << ' ' << minY << ' ' << contrib << '\n';
                ans[i] += contrib;
            }
        }

        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 < 6) 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);

    #ifdef hwe
        freopen("input.inp", "r", stdin);
        freopen("output.ans", "w", stdout);
    #else
        #define taskname ""
        if (fopen(taskname".inp", "r")) {
            freopen(taskname".inp", "r", stdin);
            freopen(taskname".out", "w", stdout);
        }
    #endif

    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';

    for (auto &x : ans) cout << x << ' ';
    cout << '\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 336 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 508 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 336 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 508 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 3 ms 336 KB Output is correct
12 Correct 4 ms 336 KB Output is correct
13 Correct 3 ms 336 KB Output is correct
14 Correct 4 ms 336 KB Output is correct
15 Correct 2 ms 336 KB Output is correct
16 Correct 3 ms 504 KB Output is correct
17 Correct 2 ms 336 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 16868 KB Output is correct
2 Correct 91 ms 17156 KB Output is correct
3 Correct 80 ms 16712 KB Output is correct
4 Correct 84 ms 16720 KB Output is correct
5 Correct 73 ms 14152 KB Output is correct

Subtask #4
0.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 336 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 508 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 3 ms 336 KB Output is correct
12 Correct 4 ms 336 KB Output is correct
13 Correct 3 ms 336 KB Output is correct
14 Correct 4 ms 336 KB Output is correct
15 Correct 2 ms 336 KB Output is correct
16 Correct 3 ms 504 KB Output is correct
17 Correct 2 ms 336 KB Output is correct
18 Execution timed out 1057 ms 15180 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 11848 KB Output is correct
2 Correct 94 ms 15940 KB Output is correct
3 Correct 117 ms 15944 KB Output is correct
4 Correct 91 ms 18504 KB Output is correct
5 Correct 96 ms 19356 KB Output is correct
6 Correct 108 ms 19272 KB Output is correct
7 Correct 86 ms 15892 KB Output is correct
8 Correct 83 ms 16088 KB Output is correct
9 Correct 89 ms 13896 KB Output is correct
10 Correct 82 ms 17736 KB Output is correct
11 Correct 77 ms 13900 KB Output is correct

Subtask #6
0.0 / 22.0

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

Subtask #7
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 16868 KB Output is correct
2 Correct 91 ms 17156 KB Output is correct
3 Correct 80 ms 16712 KB Output is correct
4 Correct 84 ms 16720 KB Output is correct
5 Correct 73 ms 14152 KB Output is correct
6 Execution timed out 1063 ms 28960 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 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 508 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 3 ms 336 KB Output is correct
13 Correct 4 ms 336 KB Output is correct
14 Correct 3 ms 336 KB Output is correct
15 Correct 4 ms 336 KB Output is correct
16 Correct 2 ms 336 KB Output is correct
17 Correct 3 ms 504 KB Output is correct
18 Correct 2 ms 336 KB Output is correct
19 Correct 97 ms 16868 KB Output is correct
20 Correct 91 ms 17156 KB Output is correct
21 Correct 80 ms 16712 KB Output is correct
22 Correct 84 ms 16720 KB Output is correct
23 Correct 73 ms 14152 KB Output is correct
24 Execution timed out 1057 ms 15180 KB Time limit exceeded
25 Halted 0 ms 0 KB -