Submission #853902

#	Time	Username	Problem	Language	Result	Execution time	Memory
853902		vuavisao	Land of the Rainbow Gold (APIO17_rainbow)	C++17	0 / 100	1 ms	348 KiB

rainbow

#ifndef LOCAL
    #include "rainbow.h"
#endif
#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define ll long long
using namespace std;

const int N = 1e5 + 10;
const int dx[] = {- 1, 0, 0, 1};
const int dy[] = {0, - 1, 1, 0};

struct SegTree {
    struct Node {
        int prf[2] = {0, 0}, suf[2] = {0, 0};
        int up = 0, down = 0, s = 0;
        Node() {};
        Node operator + (const Node& other) const {
            Node res;
            for(int i = 0; i < 2; ++ i) {
                res.prf[i] = this -> prf[i];
                res.suf[i] = other.suf[i];
            }
            res.up = this -> up + other.up;
            res.down = this -> down + other.down;
            res.s = this -> s + other.s;
            int have[2] = {(this -> suf[0] & other.prf[0]), (this -> suf[1] & other.prf[1])};
            res.up -= have[0];
            res.down -= have[1];
            res.s -= have[0] | have[1];
            return res;
        }
    };

    int n_node = 0;
    vector<Node> tree = {};

    void resize(int _n) { n_node = _n; tree.resize((n_node << 2) + 10); };
    SegTree() {};
    SegTree(int _n) { this -> resize(_n); };

    void update(int node, int l, int r, int idx, int val[2]) {
        if(l == r) {
            for(int i = 0; i < 2; ++ i) {
                tree[node].prf[i] = tree[node].suf[i] = val[i];
            }
            tree[node].up += val[0];
            tree[node].down += val[1];
            tree[node].s += val[0] | val[1];
            return;
        }
        int mid = (l + r) >> 1;
        if(idx <= mid) update(node << 1, l, mid, idx, val);
        else update(node << 1 | 1, mid + 1, r, idx, val);
        tree[node] = tree[node << 1] + tree[node << 1 | 1];
    }

    void Update(int idx, int val[2]) {
        return update(1, 1, n_node, idx, val);
    }

    Node query(int node, int l, int r, int L, int R) {
        if(l > r || L > R || l > R || L > r) return Node();
        if(L <= l && r <= R) return tree[node]; 
        int mid = (l + r) >> 1;
        if(R <= mid) return query(node << 1, l, mid, L, R);
        else if(L > mid) return query(node << 1 | 1, mid + 1, r, L, R);
        return query(node << 1, l, mid, L, R) + query(node << 1 | 1, mid + 1, r, L, R);
    }

    Node Query(int l, int r) {
        return query(1, 1, n_node, l, r);
    }
};

int n, m, q;
int len, x, y;
char s[N];

bool un_go[3][200010];
SegTree st;

void init(int R, int C, int sr, int sc, int M, char *S) {
    n = R; m = C; x = sr; y = sc; len = M;
    for(int i = 0; i < len; ++ i) s[i] = S[i];

    un_go[x][y] = true;
    for(int i = 0; i < len; ++ i) {
        if(s[i] == 'N') -- x;
        else if(s[i] == 'S') ++ x;
        else if(s[i] == 'E') ++ y;
        else -- y;
        un_go[x][y] = true;
    }

    st.resize(m);
    for(int i = 1; i <= m; ++ i) {
        int val[2] = {un_go[1][i], un_go[2][i]};
        st.Update(i, val);
    }
}

int colour(int ar, int ac, int br, int bc) {
    int up = ar, le = ac, down = br, ri = bc;
    const auto& res = st.Query(le, ri);
    if(up == down) {
        if(up == 1) return res.up;
        else return res.down;
    } 
    else return res.s;
}

/// Code by vuavisao

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