Submission #1128429

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128429		Zero_OP	Land of the Rainbow Gold (APIO17_rainbow)	C++17	100 / 100	754 ms	79652 KiB

rainbow

/*

The planar graph : First, draw a "bound river" rectangle

For example, the query :
("r" means river cell, "." means empty cell)

....rrrrr..
rrr....r...
..r....rrr.
rrr.....r..

Draw a "bound river" rectangle
=>

rrrrrrrrrrrrr
r....rrrrr..r
rrrr....r...r
r..r....rrr.r
rrrr.....r..r
rrrrrrrrrrrrr

- vertexes = number of r
- edges = number of adjacent pairs r <-> r
- *faces = number of 2x2s of r
- connected components = if the whole river is "strictly" inside the rectangle => connected components = 2, otherwise cc = 1
- answer = *faces - *(number of block 2x2s of r)

For example :
rrrrrrrr
r......r
r..rr..r
r......r
rrrrrrrr
so cc = 2

Special Case :
..rrrr
..r..r
...rrr
just need 1 more segment tree 2d

Euler Polyhedron Formula : V - E + F = 1 + C
*/

#include "bits/stdc++.h"
#ifndef LOCAL
    #include "rainbow.h"
#endif

using namespace std;

#define rep(i, l, r) for(int i = (l); i < (r); ++i)
#define sz(v) (int)v.size()
#define dbg(x) "[" #x " = " << (x) << "]"
#define all(v) begin(v), end(v)
#define compact(v) v.erase(unique(all(v)), end(v))
#define file(name) if(fopen(name".inp", "r")){ freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }

template<typename T>
    bool minimize(T& a, const T& b){
        if(a > b){
            return a = b, true;
        }
        return false;
    }

template<typename T>
    bool maximize(T& a, const T& b){
        if(a < b){
            return a = b, true;
        }
        return false;
    }

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

using ll = long long;
using ld = long double;
using ull = unsigned long long;
using vi = vector<int>;
using vl = vector<ll>;

const int MAX = 1e5 + 5;
const int MAXNODES = MAX * 5 * 17;

int used;
struct node{
    int ln, rn, sum;
} st[MAXNODES];

int build(int l, int r){
    if(l == r) return ++used;
    int mid = l + r >> 1, cur = ++used;
    st[cur].ln = build(l, mid);
    st[cur].rn = build(mid + 1, r);
    return cur;
}

void refine(int nd){
    st[nd].sum = st[st[nd].ln].sum + st[st[nd].rn].sum;
}

int update(int nd, int l, int r, int pos, int val){
    if(l == r){
        ++used;
        st[used].sum = st[nd].sum + val;
        return used;
    } else{
        int mid = l + r >> 1, cur = ++used;
        st[cur].ln = st[nd].ln;
        st[cur].rn = st[nd].rn;
        if(pos <= mid) st[cur].ln = update(st[nd].ln, l, mid, pos, val);
        else st[cur].rn = update(st[nd].rn, mid + 1, r, pos, val);
        refine(cur);
        return cur;
    }
}

int query(int vl, int vr, int l, int r, int u, int v){
    if(v < l || u > r) return 0;
    if(u <= l && r <= v) return st[vr].sum - st[vl].sum;
    int mid = l + r >> 1;
    return query(st[vl].ln, st[vr].ln, l, mid, u, v) + query(st[vl].rn, st[vr].rn, mid + 1, r, u, v);
}

struct tree2d{
    int bound;
    vector<int> rt;
    vector<pair<int, int>> pts;

    tree2d() : rt(), pts(), bound() {}
    tree2d(int n, int m) : rt(n + 1), bound(m), pts() {}

    void add(const pair<int, int>& p){
        pts.emplace_back(p);
    }

    void construct(){
        if(bound == 0) return;
        sort(all(pts));
        rt[0] = build(1, bound);
        for(int i = 1, j = 0; i < sz(rt); ++i){
            rt[i] = rt[i - 1];
            while(j < sz(pts) && pts[j].first == i){
                rt[i] = update(rt[i], 1, bound, pts[j].second, +1);
                ++j;
            }
        }
    }

    int query2d(int l, int r, int u, int v){
        if(l > r || u > v) return 0;
        return query(rt[l - 1], rt[r], 1, bound, u, v);
    }
} horizontal_edges, vertical_edges, vertices, blocks, special_edges;

int min_x, max_x, min_y, max_y;

void init(int R, int C, int x, int y, int M, char *S) {
    set<pair<int, int>> rivers;
    min_x = 1e9;
    max_x = -1e9;
    min_y = 1e9;
    max_y = -1e9;
    for(int i = 0; i <= M; ++i){
        rivers.insert({x, y});
        minimize(min_x, x);
        maximize(max_x, x);
        minimize(min_y, y);
        maximize(max_y, y);

        if(i < M){
            if(S[i] == 'N') --x;
            if(S[i] == 'S') ++x;
            if(S[i] == 'W') --y;
            if(S[i] == 'E') ++y;
        }
    }

    horizontal_edges = tree2d(R, C);
    vertical_edges = tree2d(R, C);
    vertices = tree2d(R, C);
    blocks = tree2d(R, C);
    special_edges = tree2d(R, C);

    for(auto [x, y] : rivers){
        vertices.add({x, y});
        //(x + 1, y) -> vertical
        bool vert = false, horz = false;
        if(rivers.count({x, y + 1})){
            vertical_edges.add({x, y});
            vert = true;
        }

        //(x, y + 1) -> horizontal
        if(rivers.count({x + 1, y})){
            horizontal_edges.add({x, y});
            horz = true;
        }

        if(vert && horz && rivers.count({x + 1, y + 1})){
            blocks.add({x, y});
        }

        if(rivers.count({x - 1, y + 1}) && !rivers.count({x - 1, y}) && !rivers.count({x, y + 1})){
            special_edges.add({x - 1, y});
        }

        if(rivers.count({x + 1, y + 1}) && !rivers.count({x + 1, y}) && !rivers.count({x, y + 1})){
            special_edges.add({x, y});
        }
    }

    horizontal_edges.construct();
    vertical_edges.construct();
    vertices.construct();
    blocks.construct();
    special_edges.construct();
}

int count_vertices(int x1, int y1, int x2, int y2){
    int cur = vertices.query2d(x1, x2, y1, y2);
    int side = ((x2 - x1 + 1) + (y2 - y1 + 1)) * 2 + 4;
    return cur + side;
}

int count_edges(int x1, int y1, int x2, int y2){
    int side = ((x2 - x1 + 1) + (y2 - y1 + 1)) * 2 + 4;
    int horz = horizontal_edges.query2d(x1, x2 - 1, y1, y2);
    int vert = vertical_edges.query2d(x1, x2, y1, y2 - 1);
    int left_side = vertices.query2d(x1, x1, y1, y2);
    int right_side = vertices.query2d(x2, x2, y1, y2);
    int up_side = vertices.query2d(x1, x2, y1, y1);
    int down_side = vertices.query2d(x1, x2, y2, y2);
    int extra = special_edges.query2d(x1, x2 - 1, y1, y2 - 1);
    return side + horz + vert + left_side + right_side + up_side + down_side + extra;
}

int count_connected_components(int x1, int y1, int x2, int y2){
    int extra = (x1 < min_x && max_x < x2 && y1 < min_y && max_y < y2);
    return 1 + extra;
}

int count_blocks(int x1, int y1, int x2, int y2){
    int inside = blocks.query2d(x1, x2 - 1, y1, y2 - 1);
    int l = vertical_edges.query2d(x1, x1, y1, y2 - 1);
    int r = vertical_edges.query2d(x2, x2, y1, y2 - 1);
    int d = horizontal_edges.query2d(x1, x2 - 1, y1, y1);
    int u = horizontal_edges.query2d(x1, x2 - 1, y2, y2);
    int x1y1 = vertices.query2d(x1, x1, y1, y1);
    int x1y2 = vertices.query2d(x1, x1, y2, y2);
    int x2y1 = vertices.query2d(x2, x2, y1, y1);
    int x2y2 = vertices.query2d(x2, x2, y2, y2);
    return inside + l + r + d + u + x1y1 + x1y2 + x2y1 + x2y2;
}

int colour(int ar, int ac, int br, int bc){
    int V = count_vertices(ar, ac, br, bc);
    int E = count_edges(ar, ac, br, bc);
    int C = count_connected_components(ar, ac, br, bc);
    int blocks = count_blocks(ar, ac, br, bc);
    return E - V + C - blocks;
}

#ifdef LOCAL
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);

    int R, C, M, Q, sr, sc;
    cin >> R >> C >> M >> Q >> sr >> sc;

    char S[M];
    for(int i = 0; i < M; ++i) cin >> S[i];

    init(R, C, sr, sc, M, S);

    while(Q--){
        int ar, ac, br, bc;
        cin >> ar >> ac >> br >> bc;
        cout << colour(ar, ac, br, bc) << '\n';
    }


    return 0;
}
#endif // LOCAL

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