Submission #263503

#	Time	Username	Problem	Language	Result	Execution time	Memory
263503		Kastanda	Land of the Rainbow Gold (APIO17_rainbow)	C++11	50 / 100	1061 ms	104048 KiB

rainbow

// M
#include<bits/stdc++.h>
#include "rainbow.h"
#define lc (id << 1)
#define rc (lc ^ 1)
#define md ((l + r) >> 1)
using namespace std;
const int N = 200005;
int n, m;
vector < int > V[3][N], VS[3][N * 2], R[2][N], C[2][N];
vector < pair < int , int > > A;
map < int , int > MP[N];
inline int Count(vector < int > &vec, int l, int r)
{
        // [l, r)
        return (int)(lower_bound(vec.begin(), vec.end(), r) - lower_bound(vec.begin(), vec.end(), l));
}
void Build(int id = 1, int l = 1, int r = n + 1)
{
        if (r - l < 2)
        {
                for (int w = 0; w <= 2; w ++)
                {
                        VS[w][id] = V[w][l];
                        sort(VS[w][id].begin(), VS[w][id].end());
                }
                return ;
        }
        Build(lc, l, md);
        Build(rc, md, r);
        for (int w = 0; w <= 2; w ++)
                merge(VS[w][lc].begin(), VS[w][lc].end(), VS[w][rc].begin(), VS[w][rc].end(), back_inserter(VS[w][id]));
}
int Get(int w, int le, int ri, int lq, int rq, int id = 1, int l = 1, int r = n + 1)
{
        if (ri <= l || r <= le)
                return 0;
        if (le <= l && r <= ri)
                return Count(VS[w][id], lq, rq);
        return Get(w, le, ri, lq, rq, lc, l, md) + Get(w, le, ri, lq, rq, rc, md, r);
}
void init(int _n, int _m, int sta, int stb, int k, char * S)
{
        n = _n; m = _m;
        int nwa = sta, nwb = stb;
        A.push_back(make_pair(nwa, nwb));
        for (int i = 0; i < k; i ++)
        {
                if (S[i] == 'N') nwa --;
                if (S[i] == 'S') nwa ++;
                if (S[i] == 'W') nwb --;
                if (S[i] == 'E') nwb ++;
                A.push_back(make_pair(nwa, nwb));
        }
        sort(A.begin(), A.end());
        A.resize(unique(A.begin(), A.end()) - A.begin());
        for (auto a : A)
                MP[a.first][a.second] = 1;
        // w = 0 is for vertices ..
        for (auto a : A)
                V[0][a.first].push_back(a.second);
        // w = 1 is for edges ..
        for (auto a : A)
        {
                // South :
                if (MP[a.first + 1][a.second])
                        V[1][a.first].push_back(a.second),
                        C[1][a.second].push_back(a.first);
                // East :
                if (MP[a.first][a.second + 1])
                        V[1][a.first].push_back(a.second),
                        R[1][a.first].push_back(a.second);
                // South-East :
                if (!MP[a.first][a.second + 1] && !MP[a.first + 1][a.second] && MP[a.first + 1][a.second + 1])
                        V[1][a.first].push_back(a.second);
                // South-West :
                if (!MP[a.first][a.second - 1] && !MP[a.first + 1][a.second] && MP[a.first + 1][a.second - 1])
                        V[1][a.first].push_back(a.second - 1);
                // w = 2 is for squares ..
                if (MP[a.first + 1][a.second] && MP[a.first][a.second + 1] && MP[a.first + 1][a.second + 1])
                        V[2][a.first].push_back(a.second);
        }
        Build();
        for (auto a : A)
                R[0][a.first].push_back(a.second),
                C[0][a.second].push_back(a.first);
        for (int i = 1; i <= n; i ++)
                for (int w = 0; w <= 1; w ++)
                        sort(R[w][i].begin(), R[w][i].end());
        for (int i = 1; i <= m; i ++)
                for (int w = 0; w <= 1; w ++)
                        sort(C[w][i].begin(), C[w][i].end());
}
int colour(int lx, int ly, int rx, int ry)
{
        // Note : if no river cell is on the border, then c = 2.
        // v - e + f = 1 + c  ~~~>  f = e - v + 1 + c
        // sq : number of 2*2 squares
        // Then the answer is f-1 - sq
        int v = Get(0, lx, rx + 1, ly, ry + 1);

        if (v == 0) // No river cell
                return 1;

        v += (rx - lx + 1 + ry - ly + 1) * 2 + 4;

        int e = Get(1, lx, rx, ly, ry) + (rx - lx + 1 + ry - ly + 1) * 2 + 4;

        int stamp = e;

        e += Count(R[0][lx], ly, ry + 1);
        e += Count(R[0][rx], ly, ry + 1);
        e += Count(C[0][ly], lx, rx + 1);
        e += Count(C[0][ry], lx, rx + 1);

        int c = 1;
        if (e == stamp) // There is no border river cell
                c = 2;

        e += Count(R[1][rx], ly, ry);
        e += Count(C[1][ry], lx, rx);

        int sq = MP[lx][ly] + MP[lx][ry] + MP[rx][ly] + MP[rx][ry];

        sq += Get(2, lx, rx, ly, ry);
        sq += Count(R[1][lx], ly, ry);
        sq += Count(R[1][rx], ly, ry);
        sq += Count(C[1][ly], lx, rx);
        sq += Count(C[1][ry], lx, rx);

        /*printf("v is : %d\n", v);
        printf("e is : %d\n", e);
        printf("c is : %d\n", c);
        printf("sq is : %d\n", sq);*/

        int f = e - v + 1 + c;

        //printf("f is : %d\n", f);

        return f-1 - sq;

}

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