Submission #249272

#	Time	Username	Problem	Language	Result	Execution time	Memory
249272		SamAnd	Land of the Rainbow Gold (APIO17_rainbow)	C++17	0 / 100	3113 ms	909000 KiB

rainbow

#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
const int N = 200005;
const int xx[4] = {-1, 1, 0, 0};
const int yy[4] = {0, 0, -1, 1};
const char cc[4] = {'N', 'S', 'W', 'E'};

int n, m;

set<pair<int, int> > s;

int minx, maxx, miny, maxy;

set<pair<int, int> > c;

void dfs(int x, int y, int x1, int y1_, int x2, int y2)
{
    if (!(x1 <= x && x <= x2))
        return;
    if (!(y1_ <= y && y <= y2))
        return;
    if (s.find(m_p(x, y)) != s.end())
        return;
    if (c.find(m_p(x, y)) != c.end())
        return;
    c.insert(m_p(x, y));
    minx = min(minx, x);
    maxx = max(maxx, x);
    miny = min(miny, y);
    maxy = max(maxy, y);
    for (int i = 0; i < 4; ++i)
    {
        int hx = x + xx[i];
        int hy = y + yy[i];
        dfs(hx, hy, x1, y1_, x2, y2);
    }
}

vector<int> ul[3], ur[3];

void init(int R, int C, int sx, int sy, int ss, char *s)
{
    n = R;
    m = C;
    vector<pair<int, int> > v;
    v.push_back(m_p(sx, sy));
    for (int i = 0; i < ss; ++i)
    {
        for (int j = 0; j < 4; ++j)
        {
            if (cc[j] == s[i])
            {
                v.push_back(m_p(v.back().fi + xx[j], v.back().se + yy[j]));
            }
        }
    }
    for (int i = 0; i < v.size(); ++i)
    {
        ::s.insert(v[i]);
    }

    if (n == 2)
    {
        for (int j = 1; j <= m; ++j)
        {
            for (int i = 1; i <= n; ++i)
            {
                if (c.find(m_p(i, j)) == c.end())
                {
                    minx = maxx = i;
                    miny = maxy = j;
                    dfs(i, j, 1, 1, 2, m);
                    ul[0].push_back(miny);
                    ur[0].push_back(maxy);
                }
            }
        }
        for (int i = 1; i <= 2; ++i)
        {
            for (int j = 1; j <= n; ++j)
            {
                if (::s.find(m_p(i, j)) == ::s.end())
                {
                    if (j == 1 || ::s.find(m_p(i, j - 1)) != ::s.end())
                    {
                        ul[i].push_back(j);
                    }
                    if (j == m || ::s.find(m_p(i, j + 1)) != ::s.end())
                    {
                        ur[i].push_back(j);
                    }
                }
            }
        }
    }

    /*minx = maxx = sx;
    miny = maxy = sy;
    for (int i = 0; i < v.size(); ++i)
    {
        minx = min(minx, v[i].fi);
        maxx = max(maxx, v[i].fi);
        miny = min(miny, v[i].se);
        maxy = max(maxy, v[i].se);
    }*/
}

int colour(int x1, int y1_, int x2, int y2)
{
    /*if (max(x1, minx) > min(x2, maxx))
        return 0;
    if (max(y1_, miny) > max(y2, maxy))
        return 0;*/
    /*x1 = max(x1, minx - 2);
    x2 = min(x2, maxx + 2);
    y1_ = max(y1_, miny - 2);
    y2 = min(y2, maxy + 2);*/

    if (n == 2)
    {
        int z;
        if (x1 < x2)
            z = 0;
        else
            z = x1;
        int l = upper_bound(all(ul[z]), y2) - ul[z].begin();
        int r = lower_bound(all(ur[z]), y1_) - ur[z].begin();
        if (l > r)
            return 0;
        return r - l + 1;
    }

    c.clear();

    int ans = 0;
    for (int x = x1; x <= x2; ++x)
    {
        for (int y = y1_; y <= y2; ++y)
        {
            if (s.find(m_p(x, y)) != s.end())
                continue;
            if (c.find(m_p(x, y)) == c.end())
            {
                ++ans;
                dfs(x, y, x1, y1_, x2, y2);
            }
        }
    }
    return ans;
}

Compilation message (stderr)

rainbow.cpp: In function 'void init(int, int, int, int, int, char*)':
rainbow.cpp:64:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < v.size(); ++i)
                     ~~^~~~~~~~~~

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