Submission #920627

#	Time	Username	Problem	Language	Result	Execution time	Memory
920627		danikoynov	Land of the Rainbow Gold (APIO17_rainbow)	C++14	100 / 100	931 ms	423508 KiB

rainbow

#include "rainbow.h"
#include<bits/stdc++.h>

using namespace std;

const int inf = 1e9;

const int maxn = 2e5 + 10;

struct node
{
    int lc, rc, sum;

    node()
    {
        lc = rc = -1;
        sum = 0;
    }
};


struct persistent_segment_tree
{
    node tree[30 * maxn];
    int roots[maxn], last_used;
    vector < int > data[maxn];

    int update(int root, int left, int right, int pos, int val)
    {
        int new_node = ++ last_used;
        if (root != -1)
            tree[new_node] = tree[root];
        if (left == right)
        {
            tree[new_node].sum += val;
            return new_node;
        }

        int mid = (left + right) / 2;
        if (pos <= mid)
            tree[new_node].lc = update(tree[new_node].lc, left, mid, pos, val);
        else
            tree[new_node].rc = update(tree[new_node].rc, mid + 1, right, pos, val);

        tree[new_node].sum = 0;
        if (tree[new_node].lc != -1)
            tree[new_node].sum += tree[tree[new_node].lc].sum;
                if (tree[new_node].rc != -1)
            tree[new_node].sum += tree[tree[new_node].rc].sum;

        return new_node;
    }

    int query(int root, int left, int right, int qleft, int qright)
    {
        if (left > qright || right < qleft || root == -1)
            return 0;
        if (left >= qleft && right <= qright)
            return tree[root].sum;

        int mid = (left + right) / 2;
        return query(tree[root].lc, left, mid, qleft, qright) +
                query(tree[root].rc, mid + 1, right, qleft, qright);
    }


    void init(set < pair < int, int > > &my_set)
    {
        last_used = 0;
        for (pair < int, int > cur : my_set)
        {
            data[cur.first].push_back(cur.second);
        }

        roots[0] = -1;
        for (int i = 1; i < maxn; i ++)
        {
            roots[i] = roots[i - 1];
            for (int cur : data[i])
            {
                roots[i] = update(roots[i], 1, maxn - 1, cur, 1);
            }
        }
    }
    int query_rectangle(int lb, int rb, int dw, int up)
    {
        return query(roots[rb], 1, maxn - 1, dw, up) -
                query(roots[lb - 1], 1, maxn - 1, dw, up);
    }
};

persistent_segment_tree river_tree;
persistent_segment_tree nodes_tree;
persistent_segment_tree ver_tree;
persistent_segment_tree hor_tree;

set < pair < int, int > > nodes, ver_edges, hor_edges, river;

int min_x = inf, max_x = -inf, min_y = inf, max_y = -inf;


struct fenwick_2d
{
    map < int, int > data[maxn];
    vector < int > vec[maxn], pref[maxn];

    void build()
    {


        for (int i = 0; i < maxn; i ++)
        {
            vec[i].push_back(0);
            pref[i].push_back(0);
            for (pair < int, int > cur : data[i])
            {
                //if (i == 2)
                {
                    //cout << cur.first << " ------- " << cur.second << " " << vec[i].back().second << endl;
                }
                int new_val = pref[i].back() + cur.second;
                vec[i].push_back(cur.first);
                pref[i].push_back(new_val);
            }
        }

        /**for (int i = 0; i < 10; i ++)
        {
            cout << "step " << i << endl;
            for (int cur : vec[i])
                cout << cur << " ";
            cout << endl;
        }*/
    }

    void add(int pos, int val)
    {
        for (int i = pos; i < maxn; i += (i & -i))
        {
            data[i][val] ++;
        }
    }

    int bin_search(int idx, int val)
    {
        int lf = 0, rf = (int)(vec[idx].size()) - 1;
        while(lf <= rf)
        {
            int mf = (lf + rf) / 2;
            if (vec[idx][mf] <= val)
                lf = mf + 1;
            else
                rf = mf - 1;
        }
        return lf;
    }

    int query(int pos, int lb, int rb)
    {
        ///cout << "QUERY " << pos << " " << lb << " " << rb << endl;
        int ans = 0;
        for (int i = pos; i > 0; i -= (i & -i))
        {

            int left = bin_search(i, lb - 1), right = bin_search(i, rb);
            //cout << "left right " << left << " " << right << " " << vec[i][left].second << " :: " << vec[i][right].second << endl;
            ans = ans + (pref[i][right - 1 ]- pref[i][left - 1]);
        }
        //cout << "Ans " << ans << endl;
        return ans;
    }

    int range_query(int from, int to, int lb, int rb)
    {
        return query(to, lb, rb) - query(from - 1, lb, rb);
    }
};

fenwick_2d fen_river;
fenwick_2d fen_nodes;
fenwick_2d fen_hor;
fenwick_2d fen_ver;


void add_node(int x, int y)
{
    nodes.insert({x, y});
}

void add_hor_edge(int x, int y)
{
    hor_edges.insert({x, y});
}

void add_ver_edge(int x, int y)
{
    ver_edges.insert({x, y});
}

void add_river(int x, int y)
{
    add_node(x, y);
    add_node(x, y + 1);
    add_node(x + 1, y);
    add_node(x + 1, y + 1);
    add_hor_edge(x, y);
    add_hor_edge(x + 1, y);
    add_ver_edge(x, y);
    add_ver_edge(x, y + 1);
    min_x = min(min_x, x);
    max_x = max(max_x, x);
    min_y = min(min_y, y);
    max_y = max(max_y, y);
    river.insert({x, y});

}

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

        add_river(sr, sc);
    }

    /**for (pair < int, int > cur : river)
    {
        fen_river.add(cur.first, cur.second);
    }
    for (pair < int, int > cur : nodes)
    {
        fen_nodes.add(cur.first, cur.second);
    }
    for (pair < int, int > cur : hor_edges)
    {
        fen_hor.add(cur.first, cur.second);
    }
    for (pair < int, int > cur : ver_edges)
    {
        fen_ver.add(cur.first, cur.second);
    }
    fen_river.build();
    fen_nodes.build();
    fen_hor.build();
    fen_ver.build();*/

    river_tree.init(river);
    nodes_tree.init(nodes);
    ver_tree.init(ver_edges);
    hor_tree.init(hor_edges);

}

int query_nodes(int ar, int ac, int br, int bc)
{
    int cnt = 0;
    for (pair < int, int > cur : nodes)
    {
        if (cur.first >= ar && cur.first <= br &&
                cur.second >= ac && cur.second <= bc)
            cnt ++;
    }
    return cnt;
}

int query_hor_edges(int ar, int ac, int br, int bc)
{
    int cnt = 0;
    for (pair < int, int > cur : hor_edges)
    {
        if (cur.first >= ar && cur.first <= br &&
                cur.second >= ac && cur.second <= bc)
            cnt ++;
    }
    return cnt;
}

int query_ver_edges(int ar, int ac, int br, int bc)
{
    int cnt = 0;
    for (pair < int, int > cur : ver_edges)
    {
        if (cur.first >= ar && cur.first <= br &&
                cur.second >= ac && cur.second <= bc)
            cnt ++;
    }
    return cnt;
}

int query_river(int ar, int ac, int br, int bc)
{
    int cnt = 0;
    for (pair < int, int > cur : river)
    {
        if (cur.first >= ar && cur.first <= br &&
                cur.second >= ac && cur.second <= bc)
            cnt ++;
    }
    return cnt;
}

int colour(int ar, int ac, int br, int bc)
{
    int V = nodes_tree.query_rectangle(ar + 1, br, ac + 1, bc);///fen_nodes.range_query(ar + 1, br, ac + 1, bc) ;
    int E = 0;
    E = E + hor_tree.query_rectangle(ar + 1, br, ac, bc);
    E = E + ver_tree.query_rectangle(ar, br, ac + 1, bc);
    int C = 1;

    if (ar < min_x && ac < min_y && br > max_x && bc > max_y)
        C ++;
    /// V + F = E + C + 1
    /// F = E - V + C + 1

    int F = E - V + C - river_tree.query_rectangle(ar, br, ac, bc);///fen_river.range_query(ar, br, ac, bc); //query_river(ar, ac, br, bc);
    ///cout << "V " << V << " E " << E << " C " << C << endl;
    //cout << "Faces " << F << endl;
    ///exit(0);
    return F;

}

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