제출 #1160255

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1160255		JahonaliX	모자이크 (IOI24_mosaic)	C++20	100 / 100	527 ms	203908 KiB

mosaic

#include <bits/stdc++.h>

using namespace std;

vector<long long>
mosaic(vector<int> X, std::vector<int> Y, vector<int> T, std::vector<int> B, vector<int> L, std::vector<int> R) {
    vector<long long> ans;
    int n = (int) X.size(), q = (int) T.size();
    unordered_map<int, unordered_map<int, long long>> a, b;
    unordered_map<int, long long> s;
    for (int i = 0; i < n; ++i) a[0][i] = X[i];
    for (int i = 0; i < n; ++i) a[i][0] = Y[i];
    for (int i = 1; i < 3; ++i) for (int j = 1; j < n; ++j) a[i][j] = !a[i - 1][j] && !a[i][j - 1];
    for (int j = 1; j < 3; ++j) for (int i = 1; i < n; ++i) a[i][j] = !a[i - 1][j] && !a[i][j - 1];
    b = a;
    for (int i = n - 1; i > 1; --i) s[i] = a[2][i];
    for (int i = 3; i < n; ++i) s[4 - i] = a[i][2];
    for (int i = n - 2; i > 4 - n; --i) s[i] += s[i + 1];
    for (int i = n - 2; i > 4 - n; --i) s[i] += s[i + 1];
    for (int j = 0; j < 3; ++j) for (int i = 1; i < n; ++i) b[i][j] += b[i - 1][j];
    for (int j = 0; j < 3; ++j) for (int i = 1; i < n; ++i) a[j][i] += a[j][i - 1];
    for (int i = 0; i < q; ++i) {
        long long c = 0;
        while (T[i] <= B[i] && T[i] < 3) c += a[T[i]][R[i]] - a[T[i]++][L[i] - 1];
        while (L[i] <= R[i] && L[i] < 3) c += b[B[i]][L[i]] - b[T[i] - 1][L[i]++];
        if (T[i] <= B[i] && L[i] <= R[i]) {
            L[i] -= B[i] - 2;
            R[i] -= B[i] - 2;
            c += s[L[i]] - s[R[i] + 1] - s[L[i] + B[i] - T[i] + 1] + s[R[i] + B[i] - T[i] + 2];
        }
        ans.emplace_back(c);
    }
    return ans;
}

//int main() {
////    for (long long i: mosaic({1, 0, 1, 1, 0}, {1, 1, 0, 1, 1},
////                             {0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4},
////                             {0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4},
////                             {0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 1, 2, 3, 4},
////                             {0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 1, 2, 3, 4}))
////        cout << i;
////    for (long long i: mosaic({1, 0, 1, 1, 0}, {1, 1, 0, 1, 1},
////                             {0, 1, 2, 3, 4}, {0, 1, 2, 3, 4}, {0, 0, 0, 0, 0}, {4, 4, 4, 4, 4}))
////        cout << i;
//    cout << mosaic({0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {8}, {9}, {9}, {9})[0];
//    return 0;
//}
/*
10110
10001
01010
10101
10010
*/
/*
0000000000
0101010101
0010101010
0101010101
0010101010
0101010101
0010101010
0101010101
0010101010
0101010101
 */

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