Submission #384186

#	Time	Username	Problem	Language	Result	Execution time	Memory
384186		BartolM	Land of the Rainbow Gold (APIO17_rainbow)	C++17	100 / 100	1406 ms	172524 KiB

rainbow

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

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;

const int INF=0x3f3f3f3f;
const int N=2e5+5;
const int OFF=(1<<18);

int uk;
int lef[150*N], rig[150*N], val[150*N];
vector <int> v_br[N], v_v[N], v_ok[N], v_vod[N];

int novi(int x, int l, int r) {
    lef[uk]=l; rig[uk]=r;
    val[uk]=x;
    return uk++;
}

int upd(int ind, int pos, int lo, int hi) {
    if (ind>=hi || ind<lo) return pos;
    if (lo==hi-1) return novi(1+val[pos], 0, 0);
    int mid=(lo+hi)/2;
    return novi(1+val[pos], upd(ind, lef[pos], lo, mid), upd(ind, rig[pos], mid, hi));
}

int que(int a, int b, int pos, int lo, int hi) {
    if (!pos) return 0;
    if (lo>=b || hi<=a) return 0;
    if (lo>=a && hi<=b) return val[pos];
    int mid=(lo+hi)/2;
    return que(a, b, lef[pos], lo, mid)+que(a, b, rig[pos], mid, hi);
}

struct Tour{
    int T[N];
    Tour() {
        memset(T, 0, sizeof T);
    }
    int& operator [] (int x) {
        return T[x];
    }
    void update(int r, int c) {
        T[r]=upd(c, T[r], 0, OFF);
    }
    int query(int r1, int c1, int r2, int c2) {
        return que(c1, c2+1, T[r2], 0, OFF)-que(c1, c2+1, T[r1-1], 0, OFF);
    }
};

int mxr, mnr, mxc, mnc;

void dodaj(int r, int c) {
    v_br[r].pb(c);

    v_v[r].pb(c); v_v[r].pb(c+1);
    v_v[r+1].pb(c); v_v[r+1].pb(c+1);

    v_ok[r].pb(c); v_ok[r].pb(c+1);
    v_vod[r].pb(c); v_vod[r+1].pb(c);
    mxr=max(mxr, r); mxc=max(mxc, c);
    mnr=min(mnr, r); mnc=min(mnc, c);
}

void sazmi(vector <int> &v) {
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
}

Tour Tvod, Tok, Tv, Tbr;

void init(int R, int C, int sr, int sc, int M, char *S) {
    uk=1;
    mxr=mnr=sr; mxc=mnc=sc;
    dodaj(sr, sc);
    for (int i=0; i<M; ++i) {
        if (S[i]=='N') sr--;
        if (S[i]=='S') sr++;
        if (S[i]=='W') sc--;
        if (S[i]=='E') sc++;
        dodaj(sr, sc);
    }
    for (int i=1; i<=R+1; ++i) {
        sazmi(v_br[i]); sazmi(v_v[i]); sazmi(v_ok[i]); sazmi(v_vod[i]);
        Tbr[i]=Tbr[i-1]; Tv[i]=Tv[i-1]; Tok[i]=Tok[i-1]; Tvod[i]=Tvod[i-1];
        for (int x:v_br[i]) Tbr.update(i, x);
        for (int x:v_v[i]) Tv.update(i, x);
        for (int x:v_ok[i]) Tok.update(i, x);
        for (int x:v_vod[i]) Tvod.update(i, x);
    }
}

int colour(int r1, int c1, int r2, int c2) {
    int red=r2-r1+1, col=c2-c1+1;

    int v=Tv.query(r1+1, c1+1, r2, c2)+2*(red+col);
    int e=Tok.query(r1, c1+1, r2, c2)+Tvod.query(r1+1, c1, r2, c2)+2*(red+col);
    int comp=1;
    if (r1<mnr && r2>mxr && c1<mnc && c2>mxc) ++comp;
    int f=1-v+e+comp;
    int br=Tbr.query(r1, c1, r2, c2);
#if DEBUG
    printf("v: %d, e: %d, comp: %d\nf: %d, br: %d\n", v, e, comp, f, br);
#endif // DEBUG
    return f-br-1;
}

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