Submission #403757

#	Time	Username	Problem	Language	Result	Execution time	Memory
403757		blue	무지개나라 (APIO17_rainbow)	C++17	100 / 100	2498 ms	178872 KiB

rainbow

#include "rainbow.h"
#include <vector>
#include <set>
#include <algorithm>
using namespace std;


/*
V - E + F - C = 1

V = land cells
E = pairs of adjacent land cells
F = 2x2 grids of land cells
C = what we want

Use merge sort trees
* Blue vertices
* Blue horizontal edges (at top endpoint)
* Blue vertical edges (at left endpoint)
* 2x2 grids of white cells (at TL corner)

Also, check if a set of cells surrounding entire snake is captured in the query
  1 2 3 4
1 X X X
2 X X X
3 X X X
4 X X X
5 X X
6
*/

struct segtree
{
    int l;
    int r;
    vector<int> v;

    segtree* left = NULL;
    segtree* right = NULL;

    segtree()
    {
        ;
    }

    segtree(int L, int R)
    {
        l = L;
        r = R;

        if(l == r) return;
        int m = (l+r)/2;
        left = new segtree(l, m);
        right = new segtree(m+1, r);
    }

    void insert(int I, int V)
    {
        if(r < I || I < l) return;
        v.push_back(V);

        if(left != NULL)
        {
            left->insert(I, V);
            right->insert(I, V);
        }
    }

    void segtree_sort()
    {
        sort(v.begin(), v.end());

        if(left != NULL)
        {
            left->segtree_sort();
            right->segtree_sort();
        }
    }

    long long query(int L, int R, int V1, int V2) //count the numbers with value in [V1, V2] in range [L, R].
    {
        if(R < l || r < L) return 0;
        else if(L <= l && r <= R)
        {
            int e1 = -1, e2 = -1;
            //smallest index >= v1, largest index <= v2

            for(int bit = 19; bit >= 0; bit--)
            {
                if(e1 + (1 << bit) >= v.size()) continue;
                if(v[e1 + (1 << bit)] < V1)
                    e1 += (1 << bit);
            }
            e1++;

            for(int bit = 19; bit >= 0; bit--)
            {
                if(e2 + (1 << bit) >= v.size()) continue;
                if(v[e2 + (1 << bit)] <= V2)
                    e2 += (1 << bit);
            }

            if(e1 == v.size() || e1 == -1 || e2 == -1 || e1 > e2)
                return 0;
            else
                return e2-e1+1;
        }
        else
        {
            return left->query(L, R, V1, V2) + right->query(L, R, V1, V2);
        }
    }
};

segtree cells(0, 200001);
segtree horiz(0, 200001);
segtree vert(0, 200001);
segtree faces(0, 200001);

struct pos
{
    int r;
    int c;
};

bool operator < (pos A, pos B)
{
    if(A.r == B.r) return A.c < B.c;
    return A.r < B.r;
};

set<pos> water;

int tp = 1e9, lf = 1e9, dn = -1, rg = 0;

void init(int R, int C, int sr, int sc, int M, char *S)
{
    water.insert(pos{sr, sc});

    int curr_r = sr;
    int curr_c = sc;
    for(int i = 0; i < M; i++)
    {
        // cerr << S[i] << '\n';
        if(S[i] == 'N') curr_r--;
        else if(S[i] == 'S') curr_r++;
        else if(S[i] == 'W') curr_c--;
        else if(S[i] == 'E') curr_c++;
        // cerr << curr_r << ' ' << curr_c << '\n';
        water.insert(pos{curr_r, curr_c});
        // cerr << "water: ";
        // for(pos w:water) cerr << w.r << ' ' << w.c << " | ";
        // cerr << '\n';

    }

    for(pos w: water)
    {
        cells.insert(w.r, w.c);

        horiz.insert(w.r, w.c);
        if(water.find(pos{w.r, w.c-1}) == water.end())
            horiz.insert(w.r, w.c-1);

        vert.insert(w.r, w.c);
        if(water.find(pos{w.r-1, w.c}) == water.end())
            vert.insert(w.r-1, w.c);

/*
Preference order: 1 2
                  3 4
*/
        //Face DR
        faces.insert(w.r, w.c);
        // cerr << "insert " << w.r << ' ' << w.c << '\n';

        //Face DL
        if(water.find(pos{w.r, w.c-1}) == water.end())
        {
            faces.insert(w.r, w.c-1);
            // cerr << "insert " << w.r << ' ' << w.c-1 << '\n';
        }

        //Face TR
        if(water.find(pos{w.r-1, w.c}) == water.end())
            if(water.find(pos{w.r-1, w.c+1}) == water.end())
            {
                faces.insert(w.r-1, w.c);
                // cerr << "insert " << w.r-1 << ' ' << w.c << '\n';
            }

        //Face TL
        if(water.find(pos{w.r-1, w.c}) == water.end())
            if(water.find(pos{w.r, w.c-1}) == water.end())
                if(water.find(pos{w.r-1, w.c-1}) == water.end())
                {
                    faces.insert(w.r-1, w.c-1);
                    // cerr << "insert " << w.r-1 << ' ' << w.c-1 << '\n';
                }




        tp = min(tp, w.r);
        dn = max(dn, w.r);
        lf = min(lf, w.c);
        rg = max(rg, w.c);
    }

    cells.segtree_sort();
    horiz.segtree_sort();
    vert.segtree_sort();
    faces.segtree_sort();

    // cerr << tp << ' ' << dn << ' ' << lf << ' ' << rg << '\n';
}

int colour(int ar, int ac, int br, int bc)
{
    long long h = br-ar+1;
    long long w = bc-ac+1;
    /*
        V - E + F - C = 1
        C = V-E+F-1
    */
    // cerr << "check\n";
    long long V = h*w - cells.query(ar, br, ac, bc);
    long long E = h*(w-1) + (h-1)*w - vert.query(ar, br-1, ac, bc) - horiz.query(ar, br, ac, bc-1);

    long long F = (h-1)*(w-1) - faces.query(ar, br-1, ac, bc-1) + 1;

    // cerr << (tp<ar) << (br<dn) << (lf<ac) << (bc<rg) << '\n';
    if(ar < tp && dn < br && ac < lf && rg < bc)
        F++;

    long long C = V - E + F - 1;
    // cerr << V << ' ' << E << ' ' << F << ' ' << C << '\n';
    return int(C);
}

Compilation message (stderr)

rainbow.cpp: In member function 'long long int segtree::query(int, int, int, int)':
rainbow.cpp:90:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |                 if(e1 + (1 << bit) >= v.size()) continue;
      |                    ~~~~~~~~~~~~~~~~^~~~~~~~~~~
rainbow.cpp:98:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |                 if(e2 + (1 << bit) >= v.size()) continue;
      |                    ~~~~~~~~~~~~~~~~^~~~~~~~~~~
rainbow.cpp:103:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |             if(e1 == v.size() || e1 == -1 || e2 == -1 || e1 > e2)
      |                ~~~^~~~~~~~~~~

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