Submission #919289

#	Time	Username	Problem	Language	Result	Execution time	Memory
919289		boris_mihov	Land of the Rainbow Gold (APIO17_rainbow)	C++17	100 / 100	1722 ms	262532 KiB

rainbow

#include "rainbow.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <set>

typedef long long llong;
const int MAXN = 400000 + 10;
const int INF  = 1e9;

int n, m;
struct Point
{
    int x, y;
    friend bool operator < (const Point &a, const Point &b)
    {
        return a.x < b.x || (a.x == b.x && a.y < b.y);
    }
};

struct MergeSortTree
{
    std::vector <int> tree[4*MAXN];
    std::vector <Point> points;

    void build(int l, int r, int node)
    {
        if (l == r)
        {
            tree[node].push_back(points[l].y);
            return;
        }

        int mid = (l + r) / 2;
        build(l, mid, 2*node);
        build(mid + 1, r, 2*node + 1);

        int lPtr = 0, rPtr = 0;
        tree[node].reserve(r - l + 1);
        for (int i = l ; i <= r ; ++i)
        {
            if (lPtr == tree[2*node].size())
            {
                tree[node].push_back(tree[2*node + 1][rPtr++]);
                continue;
            }

            if (rPtr == tree[2*node + 1].size())
            {
                tree[node].push_back(tree[2*node][lPtr++]);
                continue;
            }

            if (tree[2*node][lPtr] < tree[2*node + 1][rPtr])
            {
                tree[node].push_back(tree[2*node][lPtr++]);
            } else
            {
                tree[node].push_back(tree[2*node + 1][rPtr++]);
            }
        }
    }

    int countLess(int node, int value)
    {
        int l = -1, r = tree[node].size(), mid;
        while (l < r - 1)
        {
            mid = (l + r) / 2;
            if (tree[node][mid] <= value) l = mid;
            else r = mid;
        }

        return r;
    }

    int query(int l, int r, int node, int queryLPos, int queryRPos, int queryLVal, int queryRVal)
    {
        if (queryLPos <= l && r <= queryRPos)
        {
            return countLess(node, queryRVal) - countLess(node, queryLVal - 1);
        }

        int res = 0;
        int mid = (l + r) / 2;
        if (queryLPos <= mid) res += query(l, mid, 2*node, queryLPos, queryRPos, queryLVal, queryRVal);
        if (mid + 1 <= queryRPos) res += query(mid + 1, r, 2*node + 1, queryLPos, queryRPos, queryLVal, queryRVal);
        return res;
    }

    void build(const std::set <Point> &v)
    {
        points.reserve(v.size());
        for (const auto &[x, y] : v)
        {
            points.push_back({x, y});
        }

        if (points.size()) build(0, (int)points.size() - 1, 1);
    }

    int searchLeftPos(int value)
    {
        int l = -1, r = points.size(), mid;
        while (l < r - 1)
        {
            mid = (l + r) / 2;
            if (points[mid].x < value) l = mid;
            else r = mid;
        }

        return r;
    }

    int searchRightPos(int value)
    {
        int l = -1, r = points.size(), mid;
        while (l < r - 1)
        {
            mid = (l + r) / 2;
            if (points[mid].x <= value) l = mid;
            else r = mid;
        }

        return l;
    }

    llong query(int fromX, int fromY, int toX, int toY)
    {
        llong res = 1LL * (toX - fromX + 1) * (toY - fromY + 1);
        int left = searchLeftPos(fromX);
        int right = searchRightPos(toX);

        if (left <= right && fromY <= toY)
        {
            res -= query(0, (int)points.size() - 1, 1, left, right, fromY, toY);
        }

        return res;
    }
};

MergeSortTree vertexTree;
MergeSortTree edgesRightTree;
MergeSortTree edgesDownTree;
MergeSortTree sidesTree;

std::set <Point> vertexPoints;
std::set <Point> edgesRightPoints;
std::set <Point> edgesDownPoints;
std::set <Point> sidesPoints;
std::set <Point> s;

int minX = INF;
int minY = INF;
int maxX;
int maxY;


void init(int R, int C, int sr, int sc, int M, char *S) 
{
    n = R;
    m = C;

    for (int i = 0 ; i < M ; ++i)
    {
        minX = std::min(minX, sr);
        maxX = std::max(maxX, sr);
        minY = std::min(minY, sc);
        maxY = std::max(maxY, sc);
        s.insert({sr, sc});

        if (S[i] == 'N')
        {
            sr--;
        } else if (S[i] == 'E')
        {
            sc++;
        } else if (S[i] == 'S')
        {
            sr++;
        } else if (S[i] == 'W')
        {
            sc--;
        } else
        {
            assert(false);
        }
    }

    s.insert({sr, sc});
    minX = std::min(minX, sr);
    maxX = std::max(maxX, sr);
    minY = std::min(minY, sc);
    maxY = std::max(maxY, sc);

    for (const auto &[x, y] : s)
    {
        vertexPoints.insert({x, y});
        edgesRightPoints.insert({x, y});
        edgesDownPoints.insert({x, y});
        sidesPoints.insert({x, y});
        if (x > 1) edgesDownPoints.insert({x - 1, y});
        if (y > 1) edgesRightPoints.insert({x, y - 1});
        if (x > 1) sidesPoints.insert({x - 1, y});
        if (y > 1) sidesPoints.insert({x, y - 1});
        if (x > 1 && y > 1) sidesPoints.insert({x - 1, y - 1});
    }

    vertexTree.build(vertexPoints);
    edgesRightTree.build(edgesRightPoints);
    edgesDownTree.build(edgesDownPoints);
    sidesTree.build(sidesPoints);
    return;
}

int colour(int ar, int ac, int br, int bc) 
{
    llong res = 0;
    res += vertexTree.query(ar, ac, br, bc);
    res += sidesTree.query(ar, ac, br - 1, bc - 1);
    if (ar < minX && ac < minY && br > maxX && bc > maxY) // another side
    {
        res++;
    }

    res -= edgesRightTree.query(ar, ac, br, bc - 1);
    res -= edgesDownTree.query(ar, ac, br - 1, bc);
    return res;
}

Compilation message (stderr)

rainbow.cpp: In member function 'void MergeSortTree::build(int, int, int)':
rainbow.cpp:44:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |             if (lPtr == tree[2*node].size())
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~
rainbow.cpp:50:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |             if (rPtr == tree[2*node + 1].size())
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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