Submission #843278

#	Time	Username	Problem	Language	Result	Execution time	Memory
843278		Tob	Land of the Rainbow Gold (APIO17_rainbow)	C++14	38 / 100	281 ms	307216 KiB

rainbow

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

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pii;

const int NN = 2e5 + 7, N = 4e5 + 7;

int n, m, cnt, mnx, mxx, mny, mxy;
int root[N];

map <pii, int> ma;

struct node {
    int l, r, R, E, V;
} t[150*N], I = {0, 0, 0, 0, 0};
vector <pii> wh[NN];

void Init() {
    for (int i = 1; i <= cnt; i++) t[i] = {0, 0, 0, 0, 0};
    cnt = 1;
}

node Merge(node n1, node n2, int x = 0) {
    node ne = I;
    ne.R = n1.R + n2.R;
    ne.E = n1.E + n2.E;
    ne.V = n1.V + n2.V;
    if (x) {
        ne.l = t[x].l;
        ne.r = t[x].r;
    }
    return ne;
}
void Add(int x, int y, int pos, int type, int lo = 0, int hi = N) {
    if (lo == hi) {
        t[x] = t[y];
        if (type == 0) t[x].R++;
        else if (type == 1) t[x].E++;
        else t[x].V++;
        return;
    }
    int mid = (lo + hi) / 2;
    if (pos <= mid) {
        t[x].l = ++cnt;
        t[x].r = t[y].r;
        Add(cnt, t[y].l, pos, type, lo, mid);
    }
    else {
        t[x].l = t[y].l;
        t[x].r = ++cnt;
        Add(cnt, t[y].r, pos, type, mid+1, hi);
    }
    t[x] = Merge(t[t[x].l], t[t[x].r], x);
}
void Add(int x, int pos, int type) {
    int y = ++cnt;
    Add(y, root[x], pos, type);
    root[x] = y;
}

node Query(int x, int a, int b, int lo = 0, int hi = N) {
    if (!x) return I;
    if (b < lo || hi < a) return I;
    if (a <= lo && hi <= b) return t[x];
    int mid = (lo + hi) / 2;
    return Merge(Query(t[x].l, a, b, lo, mid), Query(t[x].r, a, b, mid+1, hi));
}
node Get(int x, int y, int l, int r) {
    node X = I;
    node le = Query(root[x-1], l, r);
    node ri = Query(root[y], l, r);
    X.R = ri.R - le.R;
    X.E = ri.E - le.E;
    X.V = ri.V - le.V;
    return X;
}

void Dod(int x, int y) {
    int X = 2*x+1, Y = 2*y+1;
    
    wh[X].pb({Y, 0});

    wh[X-1].pb({Y, 1});
    wh[X+1].pb({Y, 1});
    wh[X].pb({Y-1, 1});
    wh[X].pb({Y+1, 1});

    wh[X-1].pb({Y+1, 2});
    wh[X+1].pb({Y+1, 2});
    wh[X-1].pb({Y-1, 2});
    wh[X+1].pb({Y-1, 2});
}

void init(int R, int C, int sr, int sc, int M, char *S) {
    Init();
    n = R; m = C;
    int dirx[100], diry[100];
    dirx['N'] = -1; diry['N'] = 0;
    dirx['E'] = 0; diry['E'] = 1;
    dirx['S'] = 1; diry['S'] = 0;
    dirx['W'] = 0; diry['W'] = -1;
    Dod(sc, sr);
    mnx = mxx = sr;
    mny = mxy = sc;
    for (int i = 0; i < M; i++) {
        sr += dirx[S[i]];
        sc += diry[S[i]];
        mnx = min(mnx, sr); mxx = max(mxx, sr);
        mny = min(mny, sc); mxy = max(mxy, sc);
        Dod(sc, sr);
    }
    for (int i = 1; i <= 2*C+2; i++) {
        root[i] = root[i-1];
        sort(all(wh[i]));
        wh[i].erase(unique(all(wh[i])), wh[i].end());
        for (int j = 0; j < wh[i].size(); j++) {
            Add(i, wh[i][j].F, wh[i][j].S);
        }
    }
}

int colour(int ar, int ac, int br, int bc) {
    int C = (ar >= mnx || br <= mxx || ac >= mny || bc <= mxy) ? 1 : 2;
    int x = 2*ac+1, y = 2*bc+1, l = 2*ar+1, r = 2*br+1;
    int nn = br - ar + 1, mm = bc - ac + 1;
    node X = Get(x, y, l, r);
    int R = X.R;
    int E = X.E + 2*nn + 2*mm;
    int V = X.V + 2*nn + 2*mm;
    return E - V + C - R;

    return 0;
}

Compilation message (stderr)

rainbow.cpp: In function 'void init(int, int, int, int, int, char*)':
rainbow.cpp:114:23: warning: array subscript has type 'char' [-Wchar-subscripts]
  114 |         sr += dirx[S[i]];
      |                       ^
rainbow.cpp:115:23: warning: array subscript has type 'char' [-Wchar-subscripts]
  115 |         sc += diry[S[i]];
      |                       ^
rainbow.cpp:124:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |         for (int j = 0; j < wh[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~~

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