Submission #898468

#	Time	Username	Problem	Language	Result	Execution time	Memory
898468		Tenis0206	Land of the Rainbow Gold (APIO17_rainbow)	C++11	0 / 100	741 ms	108788 KiB

rainbow

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

using namespace std;

const int nmax = 2e5;

int R, C;

map<int,bool> fr[nmax + 5];
map<int,int> r_nod[nmax + 5];
vector<int> lr[nmax + 5], lc[nmax + 5];

vector<pair<int,int>> sr[nmax + 5], sc[nmax + 5];

set<pair<int,int>> sv;

int t[5 * nmax + 5], rang[5 * nmax + 5];
int Min_r[5 * nmax + 5], Min_c[5 * nmax + 5], Max_r[5 * nmax + 5], Max_c[5 * nmax + 5];

vector<int> l_nod;
bool sel[5 * nmax + 5];

int nr_nod = 0;

int dr[] = {0,0,1,-1,1,1,-1,-1};
int dc[] = {1,-1,0,0,-1,1,-1,1};

int rep(int x)
{
    if(t[x] == x)
    {
        return x;
    }
    return (t[x] = rep(t[x]));
}

void uneste(int x, int y)
{
    x = rep(x);
    y = rep(y);
    if(x == y)
    {
        return;
    }
    if(rang[x] < rang[y])
    {
        swap(x,y);
    }
    Min_r[x] = min(Min_r[x], Min_r[y]);
    Max_r[x] = max(Max_r[x], Max_r[y]);
    Min_c[x] = min(Min_c[x], Min_c[y]);
    Max_c[x] = max(Max_c[x], Max_c[y]);
    rang[x] += rang[y];
    t[y] = x;
}

void Add(int r, int c)
{
    for(int p=0;p<4;p++)
    {
        int rr = r + dr[p];
        int cc = c + dc[p];
        if(rr >= 0 && cc >= 0 && r_nod[rr][cc])
        {
            uneste(r_nod[rr][cc], r_nod[r][c]);
        }
    }
}

void init(int RR, int CC, int r, int c, int m, char *s)
{
    R = RR;
    C = CC;
    fr[r][c] = true;
    lr[r].push_back(c);
    lc[c].push_back(r);
    vector<pair<int,int>> l;
    l.push_back({r,c});
    int Max_r_riv = r;
    for(int i=0; i<m; i++)
    {
        if(s[i] == 'S')
        {
            ++r;
        }
        else if(s[i] == 'N')
        {
            --r;
        }
        else if(s[i] == 'W')
        {
            --c;
        }
        else if(s[i] == 'E')
        {
            ++c;
        }
        if(!fr[r][c])
        {
            lr[r].push_back(c);
            lc[c].push_back(r);
            l.push_back({r,c});
        }
        fr[r][c] = true;
        Max_r_riv = max(Max_r_riv, r);
    }
    for(int i=1; i<=R; i++)
    {
        if(!lr[i].size())
        {
            continue;
        }
        sort(lr[i].begin(),lr[i].end());
        int st = 0, dr = 0;
        st = lr[i].front();
        for(int j=0; j<lr[i].size(); j++)
        {
            if(j==0 || lr[i][j] == lr[i][j - 1] + 1)
            {
                dr = lr[i][j];
            }
            else
            {
                sr[i].push_back({st,dr});
                st = lr[i][j];
            }
        }
        sr[i].push_back({st,dr});
    }
    for(int i=1; i<=C; i++)
    {
        if(!lc[i].size())
        {
            continue;
        }
        sort(lc[i].begin(),lc[i].end());
        int st = 0, dr = 0;
        st = lc[i].front();
        for(int j=0; j<lc[i].size(); j++)
        {
            if(j==0 || lc[i][j] == lc[i][j - 1] + 1)
            {
                dr = lc[i][j];
            }
            else
            {
                sc[i].push_back({st,dr});
                st = lc[i][j];
            }
        }
        sc[i].push_back({st,dr});
    }
    for(auto it : l)
    {
        r = it.first;
        c = it.second;
        for(int p=0;p<8;p++)
        {
            int rr = r + dr[p];
            int cc = c + dc[p];
            if(!fr[rr][cc])
            {
                if(sv.find({rr,cc}) == sv.end())
                {
                    r_nod[rr][cc] = (++nr_nod);
                    Min_r[nr_nod] = rr;
                    Max_r[nr_nod] = rr;
                    Min_c[nr_nod] = cc;
                    Max_c[nr_nod] = cc;
                    t[nr_nod] = nr_nod;
                    rang[nr_nod] = 1;
                }
                sv.insert({rr,cc});
            }
        }
    }
    for(auto it : l)
    {
        r = it.first;
        c = it.second;
        for(int p=0;p<8;p++)
        {
            int rr = r + dr[p];
            int cc = c + dc[p];
            if(!fr[rr][cc])
            {
                Add(rr,cc);
            }
        }
    }
    for(auto it=sv.begin();it!=sv.end();it++)
    {
        r = it->first;
        c = it->second;
        int nod = r_nod[r][c];
        nod = rep(nod);
        if(sel[nod])
        {
            continue;
        }
        if(Max_r[nod] > Max_r_riv)
        {
            continue;
        }
        l_nod.push_back(nod);
        sel[nod] = true;
    }
}

int inter(int a, int b, int c, int d)
{
    if(a > c)
    {
        swap(a,c);
        swap(b,d);
    }
    if(b < c)
    {
        return 0;
    }
    return 1;
}

int solve(vector<pair<int,int>> s, int a, int b)
{
    if(s.empty())
    {
        return 0;
    }
    int poz_a = -1, poz_b = s.size();
    int st = 0;
    int dr = s.size() - 1;
    while(st<=dr)
    {
        int mij = (st + dr) >> 1;
        if(s[mij].first <= a)
        {
            poz_a = mij;
            st = mij + 1;
        }
        else
        {
            dr = mij - 1;
        }
    }
    st = 0;
    dr = s.size() - 1;
    while(st<=dr)
    {
        int mij = (st + dr) >> 1;
        if(s[mij].second >= b)
        {
            poz_b = mij;
            dr = mij - 1;
        }
        else
        {
            st = mij + 1;
        }
    }
    if(poz_a == poz_b)
    {
        return 1;
    }
    int rez = poz_b - 1 - poz_a;
    if(poz_a != -1)
    {
        rez += inter(s[poz_a].first, s[poz_a].second, a, b);
    }
    if(poz_b != s.size())
    {
        rez += inter(s[poz_b].first, s[poz_b].second, a, b);
    }
    return rez;
}

int colour(int ar, int ac, int br, int bc)
{
    int rez = 0;
    rez += solve(sr[ar], ac, bc);
    rez += solve(sr[br], ac, bc);
    rez += solve(sc[ac], ar, br);
    rez += solve(sc[bc], ar, br);
    if(rez == 0)
    {
        ++rez;
    }
    rez -= fr[ar][ac];
    rez -= fr[ar][bc];
    rez -= fr[br][ac];
    rez -= fr[br][bc];
    for(auto it : l_nod)
    {
        if(Min_r[it] > ar && Max_r[it] < br && Min_c[it] > ac && Max_c[it] < bc)
        {
            ++rez;
        }
    }
    return rez;
}

Compilation message (stderr)

rainbow.cpp: In function 'void init(int, int, int, int, int, char*)':
rainbow.cpp:117:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |         for(int j=0; j<lr[i].size(); j++)
      |                      ~^~~~~~~~~~~~~
rainbow.cpp:140:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  140 |         for(int j=0; j<lc[i].size(); j++)
      |                      ~^~~~~~~~~~~~~
rainbow.cpp: In function 'int solve(std::vector<std::pair<int, int> >, int, int)':
rainbow.cpp:271:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  271 |     if(poz_b != s.size())
      |        ~~~~~~^~~~~~~~~~~

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