Submission #376846

#	Time	Username	Problem	Language	Result	Execution time	Memory
376846		KoD	무지개나라 (APIO17_rainbow)	C++17	100 / 100	1909 ms	304240 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);
    }
};

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 + 1 && ac < minY && bc > maxY + 1) {
        C += 1;
    }
    return V + C - E;
}

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