oj.uz

Submission #249274

# Submission time Handle Problem Language Result Execution time Memory
249274 2020-07-14T14:47:59 Z SamAnd Land of the Rainbow Gold (APIO17_rainbow) C++17
23 / 100
 3000 ms 860284 KB 
#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 (::s.find(m_p(i, j)) != ::s.end())
                    continue;
                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 <= m; ++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 r = upper_bound(all(ul[z]), y2) - ul[z].begin() - 1;
        int l = 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

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
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 384 KB Output is correct
2 Correct 136 ms 512 KB Output is correct
3 Correct 422 ms 820 KB Output is correct
4 Correct 442 ms 632 KB Output is correct
5 Correct 129 ms 512 KB Output is correct
6 Correct 0 ms 256 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 0 ms 256 KB Output is correct
9 Correct 0 ms 256 KB Output is correct
10 Correct 0 ms 256 KB Output is correct
11 Correct 322 ms 632 KB Output is correct
12 Correct 284 ms 632 KB Output is correct
13 Correct 209 ms 512 KB Output is correct
14 Correct 126 ms 512 KB Output is correct
15 Correct 0 ms 256 KB Output is correct
16 Correct 0 ms 256 KB Output is correct
17 Correct 0 ms 256 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 604 ms 48844 KB Output is correct
4 Correct 522 ms 42060 KB Output is correct
5 Correct 509 ms 43728 KB Output is correct
6 Correct 560 ms 51276 KB Output is correct
7 Correct 711 ms 51648 KB Output is correct
8 Correct 461 ms 41676 KB Output is correct
9 Correct 522 ms 42060 KB Output is correct
10 Correct 512 ms 43596 KB Output is correct
11 Correct 580 ms 51276 KB Output is correct
12 Correct 548 ms 41732 KB Output is correct
13 Correct 480 ms 41932 KB Output is correct
14 Correct 509 ms 43724 KB Output is correct
15 Correct 584 ms 51140 KB Output is correct
16 Correct 580 ms 46764 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Execution timed out 3106 ms 860284 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 384 KB Output is correct
2 Correct 136 ms 512 KB Output is correct
3 Correct 422 ms 820 KB Output is correct
4 Correct 442 ms 632 KB Output is correct
5 Correct 129 ms 512 KB Output is correct
6 Correct 0 ms 256 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 0 ms 256 KB Output is correct
9 Correct 0 ms 256 KB Output is correct
10 Correct 0 ms 256 KB Output is correct
11 Correct 322 ms 632 KB Output is correct
12 Correct 284 ms 632 KB Output is correct
13 Correct 209 ms 512 KB Output is correct
14 Correct 126 ms 512 KB Output is correct
15 Correct 0 ms 256 KB Output is correct
16 Correct 0 ms 256 KB Output is correct
17 Correct 0 ms 256 KB Output is correct
18 Execution timed out 3058 ms 34172 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 384 KB Output is correct
2 Correct 136 ms 512 KB Output is correct
3 Correct 422 ms 820 KB Output is correct
4 Correct 442 ms 632 KB Output is correct
5 Correct 129 ms 512 KB Output is correct
6 Correct 0 ms 256 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 0 ms 256 KB Output is correct
9 Correct 0 ms 256 KB Output is correct
10 Correct 0 ms 256 KB Output is correct
11 Correct 322 ms 632 KB Output is correct
12 Correct 284 ms 632 KB Output is correct
13 Correct 209 ms 512 KB Output is correct
14 Correct 126 ms 512 KB Output is correct
15 Correct 0 ms 256 KB Output is correct
16 Correct 0 ms 256 KB Output is correct
17 Correct 0 ms 256 KB Output is correct
18 Execution timed out 3058 ms 34172 KB Time limit exceeded
19 Halted 0 ms 0 KB -