Submission #376845

#	Time	Username	Problem	Language	Result	Execution time	Memory
376845		KoD	Land of the Rainbow Gold (APIO17_rainbow)	C++17	24 / 100	253 ms	28780 KiB

rainbow

#include <bits/stdc++.h>
#include "rainbow.h"

template <class T>
using Vec = std::vector<T>;

// struct Count2D {
//     int size;
//     Vec<Vec<int>> pts;
//     Vec<Vec<int>> left, right;
//     Count2D() = default;
//     Count2D(const int range) {
//         size = 1;
//         while (size < range) {
//             size <<= 1;
//         }
//         pts.resize(2 * size);
//         left.resize(size);
//         right.resize(size);
//     }
//     void add(const int x, const int y) {
//         pts[x + size].push_back(y);
//     }
//     void build() {
//         for (int i = size; i < 2 * size; ++i) {
//             std::sort(pts[i].begin(), pts[i].end());
//             pts[i].erase(std::unique(pts[i].begin(), pts[i].end()), pts[i].end());
//         }
//         for (int i = size - 1; i > 0; --i) {
//             const auto l = 2 * i;
//             const auto r = 2 * i + 1;
//             const auto l_sz = (int) pts[l].size();
//             const auto r_sz = (int) pts[r].size();
//             const auto sz = l_sz + r_sz;
//             pts[i].reserve(sz);
//             left[i].reserve(sz + 1);
//             right[i].reserve(sz + 1);
//             int s = 0, t = 0;
//             while (s < l_sz || t < r_sz) {
//                 left[i].push_back(s);
//                 right[i].push_back(t);
//                 if (t == r_sz || (s < l_sz && pts[l][s] < pts[r][t])) {
//                     pts[i].push_back(pts[l][s]);
//                     s += 1;
//                 }
//                 else {
//                     pts[i].push_back(pts[r][t]);
//                     t += 1;
//                 }
//             }
//             left[i].push_back(l_sz);
//             right[i].push_back(r_sz);
//         }
//     }
//     int count(const int xl, const int xr, int yl, int yr) const {
//         yl = std::lower_bound(pts[1].begin(), pts[1].end(), yl) - pts[1].begin();
//         yr = std::lower_bound(pts[1].begin(), pts[1].end(), yr) - pts[1].begin();
//         return count(xl, xr, yl, yr, 1, 0, size);
//     }
//     int count(const int xl, const int xr, const int yl, const int yr, const int k, const int l, const int r) const {
//         if (xl <= l && r <= xr) {
//             return yr - yl;
//         }
//         if (xr <= l || r <= xl) {
//             return 0;
//         }
//         const auto m = (l + r) / 2;
//         return count(xl, xr, left[k][yl], left[k][yr], 2 * k, l, m) + count(xl, xr, right[k][yl], right[k][yr], 2 * k + 1, m, r);
//     }
// };

struct Count2D {
    Count2D(const int _ = 0) { }
    std::set<std::pair<int, int>> set;
    void add(const int x, const int y) {
        set.emplace(x, y);
    }
    void build() {

    }
    int count(const int xl, const int xr, const int yl, const int yr) const {
        int ret = 0;
        for (const auto [x, y]: set) {
            if (xl <= x && x < xr && yl <= y && y < yr) {
                ret += 1;
            }
        }
        return ret;
    }
};

int Row, Column;
int maxX, minX, maxY, minY;
Count2D vert, edgeR, edgeC, cycle;

void add(const int x, const int y) {
    maxX = std::max(maxX, x);
    minX = std::min(minX, x);
    maxY = std::max(maxY, y);
    minY = std::min(minY, y);
    vert.add(x, y);
    edgeR.add(x, y);
    edgeC.add(x, y);
    cycle.add(x, y);
    if (x > 0) {
        edgeC.add(x - 1, y);
        cycle.add(x - 1, y);
    }
    if (y > 0) {
        edgeR.add(x, y - 1);
        cycle.add(x, y - 1);
    }
    if (x > 0 && y > 0) {
        cycle.add(x - 1, y - 1);
    }
}

void init(int R, int C, int sr, int sc, int M, char *S) {
    Row = R;
    Column = C;
    maxX = -1, minX = R, maxY = -1, minY = C;
    vert = Count2D(R);    
    edgeR = Count2D(R);    
    edgeC = Count2D(R);    
    cycle = Count2D(R);    
    sr -= 1;
    sc -= 1;
    add(sr, sc);
    for (int i = 0; i < M; ++i) {
        if (S[i] == 'N') sr -= 1;
        if (S[i] == 'S') sr += 1;
        if (S[i] == 'E') sc += 1;
        if (S[i] == 'W') sc -= 1;
        add(sr, sc);
    }
    vert.build();
    edgeR.build();
    edgeC.build();
    cycle.build();
}

int colour(int ar, int ac, int br, int bc) {
    ar -= 1;
    ac -= 1;
    long long V = 0, E = 0, C = 0;
    V += (long long) (br - ar) * (bc - ac);
    V -= vert.count(ar, br, ac, bc);
    E += (long long) (br - ar) * (bc - ac - 1);
    E -= edgeR.count(ar, br, ac, bc - 1);
    E += (long long) (br - ar - 1) * (bc - ac);
    E -= edgeC.count(ar, br - 1, ac, bc);
    C += (long long) (br - ar - 1) * (bc - ac - 1);
    C -= cycle.count(ar, br - 1, ac, bc - 1);
    if (ar < minX && br >= maxX && ac < minY && bc >= maxY) {
        C += 1;
    }
    return V + C - E;
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 12
• Subtask 3: 24 / 24
• Subtask 4: 0 / 27
• Subtask 5: 0 / 26