Submission #971255

#	Time	Username	Problem	Language	Result	Execution time	Memory
971255		CDuong	무지개나라 (APIO17_rainbow)	C++17	12 / 100	651 ms	126964 KiB

rainbow

#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;

template<class B, class T>
struct fenwick_tree_2d_sparse_sum{
    vector<B> X;
    vector<vector<array<B, 2>>> Y;
    vector<vector<T>> data;
    fenwick_tree_2d_sparse_sum() {}
    // O(n * log^2(n))
    fenwick_tree_2d_sparse_sum(vector<pair<array<B, 2>, T>> init): X(init.size()){
        sort(init.begin(), init.end());
        for(auto i = 0; i < (int)init.size(); ++ i) X[i] = init[i].first[0];
        sort(X.begin(), X.end());
        X.erase(unique(X.begin(), X.end()), X.end());
        int n = (int)X.size();
        Y.resize(n);
        data.resize(n);
        vector<vector<pair<array<B, 2>, T>>> hold(n);
        for(auto i = 0, x = 0; i < (int)init.size(); ++ i){
            auto [pos, val] = init[i];
            while(X[x] < pos[0]) ++ x;
            hold[x].push_back({{pos[1], pos[0]}, val});
        }
        for(auto x = 1; x <= n; ++ x) if(x + (x & -x) <= n){
            auto &hold0 = hold[x + (x & -x) - 1];
            auto &hold1 = hold[x - 1];
            int size = (int)hold0.size();
            hold0.insert(hold0.end(), hold1.begin(), hold1.end());
        }
        for(auto x = 0; x < n; ++ x){
            auto &Y0 = Y[x];
            auto &hold0 = hold[x];
            auto &data0 = data[x];
            sort(hold0.begin(), hold0.end());
            Y0.resize(hold0.size());
            for(auto j = 0; j < (int)hold0.size(); ++ j) Y0[j] = hold0[j].first;
            Y0.erase(unique(Y0.begin(), Y0.end()), Y0.end());
            data0.resize(Y0.size());
            for(auto j = 0, y = 0; j < (int)hold0.size(); ++ j){
                while(Y0[y] < hold0[j].first) ++ y;
                data0[y] += hold0[j].second;
            }
            int m = (int)data0.size();
            for(auto y = 1; y <= m; ++ y) if(y + (y & -y) <= m) data0[y + (y & -y) - 1] += data0[y - 1];
        }
    }
    // O(log^2(n))
    void update(B _p, B _q, T x){
        int p = lower_bound(X.begin(), X.end(), _p) - X.begin();
        assert(p < (int)X.size() && X[p] == _p);
        for(auto i = p + 1; i <= (int)X.size(); i += i & -i){
            auto &Y0 = Y[i - 1];
            auto &data0 = data[i - 1];
            int q = lower_bound(Y0.begin(), Y0.end(), array{_q, _p}) - Y0.begin();
            assert(q < (int)Y0.size() && Y0[q][0] == _q && Y0[q][1] == _p);
            for(auto j = q + 1; j <= (int)data0.size(); j += j & -j) data0[j - 1] += x;
        }
    }
    // O(log^2(n))
    T prefix(B _xr, B _yr) const{
        int xr = lower_bound(X.begin(), X.end(), _xr) - X.begin();
        T res = 0;
        for(auto i = xr; i > 0; i -= i & -i){
            auto &Y0 = Y[i - 1];
            auto &data0 = data[i - 1];
            int yr = lower_bound(Y0.begin(), Y0.end(), array{_yr, numeric_limits<B>::min()}) - Y0.begin();
            for(auto j = yr; j > 0; j -= j & -j) res += data0[j - 1];
        }
        return res;
    }
    // O(log^2(n))
    T query(B _xl, B _yl, B _xr, B _yr) const{
        if (_xl > _xr) return 0;
        if (_yl > _yr) return 0;
        return prefix(_xr, _yr) - prefix(_xl, _yr) - prefix(_xr, _yl) + prefix(_xl, _yl);
    }
    // O(log^2(n))
    T query(B _x, B _y) const{
        return prefix(_x + 1, _y + 1) - prefix(_x + 1, _y) - prefix(_x, _y + 1) + prefix(_x, _y);
    }
};

template<class T>
void compress(vector<T> &a) {
    sort(a.begin(), a.end());
    a.erase(unique(a.begin(), a.end()), a.end());
}

vector<pair<array<int, 2>, int>> vertex;
vector<pair<array<int, 2>, int>> col_edge;
vector<pair<array<int, 2>, int>> row_edge;
vector<pair<array<int, 2>, int>> river;
fenwick_tree_2d_sparse_sum<int, int> fw_vertex, fw_col_edge, fw_row_edge, fw_river;


void add_cell(int x, int y) {
    river.push_back({{x, y}, 1});

    vertex.push_back({{x, y}, 1});
    vertex.push_back({{x + 1, y}, 1});
    vertex.push_back({{x, y + 1}, 1});
    vertex.push_back({{x + 1, y + 1}, 1});

    col_edge.push_back({{x, y}, 1});
    col_edge.push_back({{x, y + 1}, 1});

    row_edge.push_back({{x, y}, 1});
    row_edge.push_back({{x + 1, y}, 1});
}

void init(int R, int C, int sr, int sc, int M, char *S) {
    --sr, --sc;
    add_cell(sr, sc);
    for (int i = 0; i < M; ++i) {
        if (S[i] == 'N') --sr;
        if (S[i] == 'S') ++sr;
        if (S[i] == 'E') ++sc;
        if (S[i] == 'W') --sc;
        add_cell(sr, sc);
    }

    compress(vertex);
    compress(col_edge);
    compress(row_edge);
    compress(river);

    fw_vertex = fenwick_tree_2d_sparse_sum(vertex);
    fw_col_edge = fenwick_tree_2d_sparse_sum(col_edge);
    fw_row_edge = fenwick_tree_2d_sparse_sum(row_edge);
    fw_river = fenwick_tree_2d_sparse_sum(river);
}

int colour(int ar, int ac, int br, int bc) {
    --ar, --ac;
    int V = 2 * (br - ar) + 2 * (bc - ac) + fw_vertex.query(ar + 1, ac + 1, br, bc);
    // cout << "V: " << V << endl;
    int E = 2 * (br - ar) + 2 * (bc - ac) + fw_col_edge.query(ar, ac + 1, br, bc) + fw_row_edge.query(ar + 1, ac, br, bc);
    // cout << "E: " << E << endl;
    int R = fw_river.query(ar, ac, br, bc);
    // cout << "R: " << R << endl;
    return E - V + 1 - R;
}

Compilation message (stderr)

rainbow.cpp: In instantiation of 'fenwick_tree_2d_sparse_sum<B, T>::fenwick_tree_2d_sparse_sum(std::vector<std::pair<std::array<B, 2>, T> >) [with B = int; T = int]':
rainbow.cpp:129:50:   required from here
rainbow.cpp:29:17: warning: unused variable 'size' [-Wunused-variable]
   29 |             int size = (int)hold0.size();
      |                 ^~~~

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