Submission #1064421

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064421		abczz	Land of the Rainbow Gold (APIO17_rainbow)	C++17	0 / 100	236 ms	68804 KiB

rainbow

#include "rainbow.h"
#include <iostream>
#include <array>
#include <algorithm>
#include <vector>
#include <map>
#define ll long long

using namespace std;

vector <array<ll, 2>> V;
map <array<ll, 2>, ll> mp, vert, edger, edgec;
string T = "NESW";
vector <ll> VR[200001], VC[200001], ER[200001], EC[200001];
ll x, y, r, c, nx, ny, tot, e, v, f, dj[4][2] = {0, 0, 0, 1, 1, 0, 1, 1}, dr[4][2] = {-1, 0, 0, 1, 1, 0, 0, -1};

void init(int R, int C, int sr, int sc, int M, char *S) {
    r = R, c = C;
    mp.clear();
    V.clear();
    V.push_back({sr, sc});
    x = sr, y = sc;
    for (int j=0; j<M; ++j) {
        auto u = S[j];
        for (int i=0; i<4; ++i) {
            if (u == T[i]) {
                nx = x + dr[i][0], ny = y + dr[i][1];
                x = nx, y = ny;
                V.push_back({x, y});
                break;
            }
        }
    }
    for (int i=0; i<V.size(); ++i) {
        --V[i][0], --V[i][1];
        x = V[i][0], y = V[i][1], tot = 0;
        if (!mp.count({x, y})) ++mp[{x, y}];
        for (int j=0; j<4; ++j) {
            nx = x + dj[j][0], ny = y + dj[j][1];
            ++vert[{nx, ny}];
        }
        ++edger[{x, y}];
        ++edger[{x+1, y}];
        ++edgec[{x, y}];
        ++edgec[{x, y+1}];
    }
    for (auto it = edger.begin(); it != edger.end();) {
        auto nx = next(it);
        auto [x, y] = it->first;
        ER[x].push_back(y);
        it = nx;
    }
    for (auto it = edgec.begin(); it != edgec.end();) {
        auto nx = next(it);
        auto [x, y] = it->first;
        EC[y].push_back(x);
        it = nx;
    }
    for (auto it = vert.begin(); it != vert.end();) {
        auto nxt = next(it);
        auto [x, y] = it->first;
        VR[x].push_back(y);
        VC[y].push_back(x);
        it = nxt;
    }
    for (int i=0; i<=R; ++i) {
        sort(VR[i].begin(), VR[i].end());
        sort(ER[i].begin(), ER[i].end());
    }
    for (int i=0; i<=C; ++i) {
        sort(VC[i].begin(), VC[i].end());
        sort(EC[i].begin(), EC[i].end());
    }
}

int colour(int ar, int ac, int br, int bc) {
    --ar, --ac;
    e = edger.size() + edgec.size() + (br-ar+bc-ac) * 2;
    auto it = lower_bound(ER[ar].begin(), ER[ar].end(), ac);
    auto it2 = lower_bound(ER[ar].begin(), ER[ar].end(), bc);
    e -= (it2-ER[ar].begin())-(it-ER[ar].begin());
    it = lower_bound(ER[br].begin(), ER[br].end(), ac);
    it2 = lower_bound(ER[br].begin(), ER[br].end(), bc);
    e -= (it2-ER[br].begin())-(it-ER[br].begin());
    it = lower_bound(EC[ac].begin(), EC[ac].end(), ar);
    it2 = lower_bound(EC[ac].begin(), EC[ac].end(), br);
    e -= (it2-EC[ac].begin())-(it-EC[ac].begin());
    it = lower_bound(EC[bc].begin(), EC[bc].end(), ar);
    it2 = lower_bound(EC[bc].begin(), EC[bc].end(), br);
    e -= (it2-EC[bc].begin())-(it-EC[bc].begin());
    v = vert.size() + (br-ar+bc-ac) * 2;
    it = lower_bound(VR[ar].begin(), VR[ar].end(), ac);
    it2 = lower_bound(VR[ar].begin(), VR[ar].end(), bc+1);
    v -= (it2-VR[ar].begin())-(it-VR[ar].begin());
    it = lower_bound(VR[br].begin(), VR[br].end(), ac);
    it2 = lower_bound(VR[br].begin(), VR[br].end(), bc+1);
    v -= (it2-ER[br].begin())-(it-ER[br].begin());
    it = lower_bound(VC[ac].begin(), VC[ac].end(), ar+1);
    it2 = lower_bound(VC[ac].begin(), VC[ac].end(), br);
    v -= (it2-VC[ac].begin())-(it-VC[ac].begin());
    it = lower_bound(VC[bc].begin(), VC[bc].end(), ar+1);
    it2 = lower_bound(VC[bc].begin(), VC[bc].end(), br);
    v -= (it2-VC[bc].begin())-(it-VC[bc].begin());
    f = e-v+1;
    return f-mp.size();
}

Compilation message (stderr)

rainbow.cpp: In function 'void init(int, int, int, int, int, char*)':
rainbow.cpp:34:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     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