oj.uz

답안 #971255

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
971255 2024-04-28T09:12:16 Z CDuong 무지개나라 (APIO17_rainbow) C++17
12 / 100
 651 ms 126964 KB 
#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

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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 344 KB Output is correct
2 Correct 7 ms 860 KB Output is correct
3 Incorrect 3 ms 436 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 245 ms 19600 KB Output is correct
4 Correct 368 ms 30408 KB Output is correct
5 Correct 362 ms 32544 KB Output is correct
6 Correct 325 ms 27116 KB Output is correct
7 Correct 368 ms 28880 KB Output is correct
8 Correct 152 ms 19388 KB Output is correct
9 Correct 354 ms 32036 KB Output is correct
10 Correct 361 ms 32240 KB Output is correct
11 Correct 317 ms 27832 KB Output is correct
12 Correct 250 ms 29940 KB Output is correct
13 Correct 257 ms 31216 KB Output is correct
14 Correct 269 ms 30820 KB Output is correct
15 Correct 264 ms 27224 KB Output is correct
16 Correct 283 ms 25324 KB Output is correct

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 221 ms 29668 KB Output is correct
3 Correct 600 ms 126964 KB Output is correct
4 Correct 651 ms 101320 KB Output is correct
5 Correct 577 ms 102760 KB Output is correct
6 Correct 162 ms 21748 KB Output is correct
7 Incorrect 217 ms 29412 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 344 KB Output is correct
2 Correct 7 ms 860 KB Output is correct
3 Incorrect 3 ms 436 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 344 KB Output is correct
2 Correct 7 ms 860 KB Output is correct
3 Incorrect 3 ms 436 KB Output isn't correct
4 Halted 0 ms 0 KB -