oj.uz

Submission #376842

# Submission time Handle Problem Language Result Execution time Memory
376842 2021-03-12T05:17:02 Z KoD Land of the Rainbow Gold (APIO17_rainbow) C++17
24 / 100
 537 ms 300532 KB 
#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 && ac < minY && bc >= maxY) {
        C += 1;
    }
    return V + C - E;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 492 KB Output is correct
2 Correct 4 ms 876 KB Output is correct
3 Incorrect 3 ms 492 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 1 ms 364 KB Output isn't correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 469 ms 295500 KB Output is correct
3 Correct 537 ms 300396 KB Output is correct
4 Correct 506 ms 296172 KB Output is correct
5 Correct 471 ms 265764 KB Output is correct
6 Correct 306 ms 193664 KB Output is correct
7 Correct 347 ms 217196 KB Output is correct
8 Correct 71 ms 19988 KB Output is correct
9 Correct 82 ms 24024 KB Output is correct
10 Correct 178 ms 108652 KB Output is correct
11 Correct 264 ms 145820 KB Output is correct
12 Correct 462 ms 295444 KB Output is correct
13 Correct 535 ms 300396 KB Output is correct
14 Correct 505 ms 296424 KB Output is correct
15 Correct 459 ms 265764 KB Output is correct
16 Correct 294 ms 188396 KB Output is correct
17 Correct 355 ms 217452 KB Output is correct
18 Correct 477 ms 295916 KB Output is correct
19 Correct 464 ms 277948 KB Output is correct
20 Correct 453 ms 277924 KB Output is correct
21 Correct 70 ms 19988 KB Output is correct
22 Correct 81 ms 23896 KB Output is correct
23 Correct 181 ms 108524 KB Output is correct
24 Correct 262 ms 145820 KB Output is correct
25 Correct 470 ms 295444 KB Output is correct
26 Correct 534 ms 300532 KB Output is correct
27 Correct 503 ms 296172 KB Output is correct
28 Correct 458 ms 265636 KB Output is correct
29 Correct 299 ms 188524 KB Output is correct
30 Correct 354 ms 217452 KB Output is correct
31 Correct 486 ms 295936 KB Output is correct
32 Correct 471 ms 277924 KB Output is correct
33 Correct 463 ms 278052 KB Output is correct

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 492 KB Output is correct
2 Correct 4 ms 876 KB Output is correct
3 Incorrect 3 ms 492 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 492 KB Output is correct
2 Correct 4 ms 876 KB Output is correct
3 Incorrect 3 ms 492 KB Output isn't correct
4 Halted 0 ms 0 KB -