Submission #731756

#	Time	Username	Problem	Language	Result	Execution time	Memory
731756		Josia	Land of the Rainbow Gold (APIO17_rainbow)	C++14	0 / 100	788 ms	195736 KiB

rainbow

#include "rainbow.h"

#include <bits/stdc++.h>

using namespace std;


// #define int int64_t



int convert(int x) {
    return x*2+1;
}




struct seg {
    struct node {
        int val=0, l=-1, r=-1;
    };


    vector<node> tree;

    seg() {
        tree.assign(2, node());
    }

    int update(int v, int rl, int rr, int pos, int x) {
        int newV = tree.size();
        tree.push_back(tree[v]);

        if (rl == rr) {
            assert(pos == rl);
            tree[newV].val += x;
            return newV;
        }

        if (tree[newV].l == -1) {tree[newV].l = tree.size(); tree.push_back(node());}
        if (tree[newV].r == -1) {tree[newV].r = tree.size(); tree.push_back(node());}
        int rm = (rl + rr)/2;
        if (pos <= rm) {
            tree[newV].l = update(tree[newV].l, rl, rm, pos, x);
        }
        else {
            tree[newV].r = update(tree[newV].r, rm+1, rr, pos, x);
        }

        tree[newV].val = tree[tree[newV].l].val + tree[tree[newV].r].val;

        return newV;
    }

    int query(int v, int rl, int rr, int ql, int qr) {
        if (ql > qr) return 0;
        if (ql == rl && qr == rr) {
            return tree[v].val;
        }

        int rm = (rl + rr)/2;
        if (tree[v].l == -1) {tree[v].l = tree.size(); tree.push_back(node());}
        if (tree[v].r == -1) {tree[v].r = tree.size(); tree.push_back(node());}
        return query(tree[v].r, rm+1, rr, max(ql, rm+1), qr) + query(tree[v].l, rl, rm, ql, min(qr, rm));
    }
};


seg squares = seg();
seg edgesFrst = seg();
seg edgesScnd = seg();
seg nodes = seg();

vector<int> queryTimeNodes;
vector<int> queryTimeSquares;
vector<int> queryTimeEdgesFrst;
vector<int> queryTimeEdgesScnd;


vector<pair<int, int>> eightConnected = {
    {1, 1},
    {-1, -1},
    {1, -1},
    {-1, 1},
    {0, 1},
    {0, -1},
    {1, 0},
    {-1, 0},
};



int R, C;

void init(signed r, signed c, signed sr, signed sc, signed M, char *S) {
    squares = seg();
    edgesFrst = seg();
    edgesScnd = seg();
    nodes = seg();


    R = r+4; C = c+4;
    R = R*2 + 1;
    C = C*2 + 1;
    map<char, pair<int, int>> dir;
    dir['N'] = {-2, 0};
    dir['S'] = {2, 0};
    dir['W'] = {0, -2};
    dir['E'] = {0, 2};


    pair<int, int> pos = {convert(sr+1), convert(sc+1)};                                                                                  // We can use 2-indexed because we added 1 margin!

    set<pair<int, int>> rivers;
    rivers.insert(pos);
    for (auto j: eightConnected) {
        rivers.insert({pos.first + j.first, pos.second + j.second});
    }

    for (int i = 0; i<M; i++) {
        pos.first += dir[S[i]].first;
        pos.second += dir[S[i]].second;

        rivers.insert(pos);

        for (auto j: eightConnected) {
            rivers.insert({pos.first + j.first, pos.second + j.second});
        }
    }


    set<pair<int, int>> eFrst, eScnd, sqrs;

    for (auto i: rivers) {
        bool scnd = rivers.count({i.first, i.second+1});
        bool frst = rivers.count({i.first+1, i.second});
        bool frstscnd = rivers.count({i.first+1, i.second+1});

        if (scnd) eScnd.insert(i);
        if (frst) eFrst.insert(i);
        if (scnd&&frst&&frstscnd) sqrs.insert(i);
    }

    queryTimeNodes.clear();
    {
        int ROW = 0;
        int root = 1;
        for (auto i: rivers) {
            while (i.first > ROW) {
                ROW++;
                queryTimeNodes.push_back(root);
            }

            root = nodes.update(root, 0, C-1, i.second, 1);
        }
        while ((int)queryTimeNodes.size() < R) queryTimeNodes.push_back(root);
    }

    queryTimeSquares.clear();
    {
        int ROW = 0;
        int root = 1;
        for (auto i: sqrs) {
            while (i.first > ROW) {
                ROW++;
                queryTimeSquares.push_back(root);
            }

            root = squares.update(root, 0, C-1, i.second, 1);
        }
        while ((int)queryTimeSquares.size() < R) queryTimeSquares.push_back(root);
    }

    queryTimeEdgesFrst.clear();
    {
        int ROW = 0;
        int root = 1;
        for (auto i: eFrst) {
            while (i.first > ROW) {
                ROW++;
                queryTimeEdgesFrst.push_back(root);
            }

            root = edgesFrst.update(root, 0, C-1, i.second, 1);
        }
        while ((int)queryTimeEdgesFrst.size() < R) queryTimeEdgesFrst.push_back(root);
    }

    queryTimeEdgesScnd.clear();
    {
        int ROW = 0;
        int root = 1;
        for (auto i: eScnd) {
            while (i.first > ROW) {
                ROW++;
                queryTimeEdgesScnd.push_back(root);
            }

            root = edgesScnd.update(root, 0, C-1, i.second, 1);
        }
        while ((int)queryTimeEdgesScnd.size() < R) queryTimeEdgesScnd.push_back(root);
    }


}

signed colour(signed ar, signed ac, signed br, signed bc) {

    ar++; ac++; br++; bc++;                                                                                        // We can use 2-indexed because we added 1 margin!

    ar = convert(ar);
    ac = convert(ac);
    br = convert(br);
    bc = convert(bc);


    int countNodes=0, countEdges=0, countSquares=0;
    bool connected=0;


    countNodes += nodes.query(queryTimeNodes[br], 0, C-1, ac, bc);
    countNodes -= nodes.query(queryTimeNodes[ar-1], 0, C-1, ac, bc);

    countEdges += edgesFrst.query(queryTimeEdgesFrst[br-1], 0, C-1, ac, bc);
    countEdges -= edgesFrst.query(queryTimeEdgesFrst[ar-1], 0, C-1, ac, bc);
    countEdges += edgesScnd.query(queryTimeEdgesScnd[br], 0, C-1, ac, bc-1);
    countEdges -= edgesScnd.query(queryTimeEdgesScnd[ar-1], 0, C-1, ac, bc-1);

    countSquares += squares.query(queryTimeSquares[br-1], 0, C-1, ac, bc-1);
    countSquares -= squares.query(queryTimeSquares[ar-1], 0, C-1, ac, bc-1);


    if (countNodes == 0) connected = 1;
    connected=connected||nodes.query(queryTimeNodes[ar], 0, C-1, ac, bc)-nodes.query(queryTimeNodes[ar-1], 0, C-1, ac, bc);
    connected=connected||nodes.query(queryTimeNodes[br], 0, C-1, ac, bc)-nodes.query(queryTimeNodes[br-1], 0, C-1, ac, bc);
    connected=connected||nodes.query(queryTimeNodes[br], 0, C-1, ac, ac)-nodes.query(queryTimeNodes[ar-1], 0, C-1, ac, ac);
    connected=connected||nodes.query(queryTimeNodes[br], 0, C-1, bc, bc)-nodes.query(queryTimeNodes[ar-1], 0, C-1, bc, bc);


    // cerr << "edges:" << countEdges << " " << "nodes:" << countNodes << " " << "squares:" << countSquares << " " <<  "connected:" << connected << "\n";

    if (!connected) {
        return countEdges-countNodes+2-countSquares;
    }


    int lenR = br-ar+1, lenC = bc-ac+1;

    countNodes+=2*(lenR+lenC)+4;

    // countNodes-=nodes.query(queryTimeNodes[ar-1], 0, C-1, ac, bc)-nodes.query(queryTimeNodes[ar-2], 0, C-1, ac, bc);
    // countNodes-=nodes.query(queryTimeNodes[br+1], 0, C-1, ac, bc)-nodes.query(queryTimeNodes[br], 0, C-1, ac, bc);
    // countNodes-=nodes.query(queryTimeNodes[br], 0, C-1, ac-1, ac-1)-nodes.query(queryTimeNodes[ar-1], 0, C-1, ac-1, ac-1);
    // countNodes-=nodes.query(queryTimeNodes[br], 0, C-1, bc+1, bc+1)-nodes.query(queryTimeNodes[ar-1], 0, C-1, bc+1, bc+1);

    countEdges+=nodes.query(queryTimeNodes[ar], 0, C-1, ac, bc)-nodes.query(queryTimeNodes[ar-1], 0, C-1, ac, bc);
    countEdges+=nodes.query(queryTimeNodes[br], 0, C-1, ac, bc)-nodes.query(queryTimeNodes[br-1], 0, C-1, ac, bc);
    countEdges+=nodes.query(queryTimeNodes[br], 0, C-1, ac, ac)-nodes.query(queryTimeNodes[ar-1], 0, C-1, ac, ac);
    countEdges+=nodes.query(queryTimeNodes[br], 0, C-1, bc, bc)-nodes.query(queryTimeNodes[ar-1], 0, C-1, bc, bc);
    
    countEdges+=2*(lenR-1+lenC-1)+8;

    // countEdges-=edgesScnd.query(queryTimeEdgesScnd[ar-1], 0, C-1, ac, bc-1)-edgesScnd.query(queryTimeEdgesScnd[ar-2], 0, C-1, ac, bc-1);
    // countEdges-=edgesScnd.query(queryTimeEdgesScnd[br+1], 0, C-1, ac, bc-1)-edgesScnd.query(queryTimeEdgesScnd[br], 0, C-1, ac, bc-1);
    // countEdges-=edgesFrst.query(queryTimeEdgesFrst[br-1], 0, C-1, ac-1, ac-1)-edgesFrst.query(queryTimeEdgesFrst[ar-1], 0, C-1, ac-1, ac-1);
    // countEdges-=edgesFrst.query(queryTimeEdgesFrst[br-1], 0, C-1, bc+1, bc+1)-edgesFrst.query(queryTimeEdgesFrst[ar-1], 0, C-1, bc+1, bc+1);

    countSquares+=edgesScnd.query(queryTimeEdgesScnd[ar], 0, C-1, ac, bc-1)-edgesScnd.query(queryTimeEdgesScnd[ar-1], 0, C-1, ac, bc-1);
    countSquares+=edgesScnd.query(queryTimeEdgesScnd[br], 0, C-1, ac, bc-1)-edgesScnd.query(queryTimeEdgesScnd[br-1], 0, C-1, ac, bc-1);
    countSquares+=edgesFrst.query(queryTimeEdgesFrst[br-1], 0, C-1, ac, ac)-edgesFrst.query(queryTimeEdgesFrst[ar-1], 0, C-1, ac, ac);
    countSquares+=edgesFrst.query(queryTimeEdgesFrst[br-1], 0, C-1, bc, bc)-edgesFrst.query(queryTimeEdgesFrst[ar-1], 0, C-1, bc, bc);



    if (nodes.query(queryTimeNodes[ar], 0, C-1, ac, ac) - nodes.query(queryTimeNodes[ar-1], 0, C-1, ac, ac)) countSquares++;
    if (nodes.query(queryTimeNodes[br], 0, C-1, ac, ac) - nodes.query(queryTimeNodes[br-1], 0, C-1, ac, ac)) countSquares++;
    if (nodes.query(queryTimeNodes[ar], 0, C-1, bc, bc) - nodes.query(queryTimeNodes[ar-1], 0, C-1, bc, bc)) countSquares++;
    if (nodes.query(queryTimeNodes[br], 0, C-1, bc, bc) - nodes.query(queryTimeNodes[br-1], 0, C-1, bc, bc)) countSquares++;




    // cerr << "edges:" << countEdges << " " << "nodes:" << countNodes << " " << "squares:" << countSquares << " " <<  "connected:" << connected << "\n";


    return countEdges-countNodes-countSquares+1;
}

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