Submission #1158348

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158348		davele	Land of the Rainbow Gold (APIO17_rainbow)	C++20	100 / 100	1140 ms	240192 KiB

rainbow

#ifndef davele
#include "rainbow.h"
#endif // davele

#include <bits/stdc++.h>
#define ll int
#define pii pair<int, int>
#define fi first
#define se second
#define vi vector <int>
#define pq priority_queue
#define MASK(i) (1ll<<(i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define x0 ___x0
#define y0 ___y0
#define div   ___div
#define next   ___next
#define prev   ___prev
#define left   ___left
#define right   ___right
#define pos pisosi
#define pb push_back
#define pf push_front
using namespace std;

//const int mod = ;
//void add (int &a, const int&b){
//    a+=b;
//    if (a>=mod) a-=mod;
//}
//
//void sub (int&a, const int&b){
//    a-=b;
//    if (a<0) a+=mod;
//}
//
//void mul (int&a, const int&b){
//    a*=b;
//    a%=mod;
//}

template<class X, class Y>
    bool minimize(X &x, const Y&y){
        if (x<=y) return false;
        else{
            x = y;
            return true;
        }
    }
template<class X, class Y>
    bool maximize (X &x, const Y&y){
        if (x>=y) return false;
        else{
            x = y;
            return true;
        }
    }

/////////////////////////////////////////////////////////////////////////////////

//// dang nhap ham
//#ifndef davele
//
//#endif // davele
//
//// chay thu ham main:
//
//#ifdef davele
//
//#endif // davele

////////////////////////////////////////////////////////////////////////////
const ll lim = 200000, limit = lim+5;

vi pos_cnt[limit], pos_vertices[limit], pos_hor[limit], pos_lan[limit];
vi bit_cnt[limit], bit_vertices[limit], bit_hor[limit], bit_lan[limit];
ll n, m, q, sx, sy, len;
string s;
vector <pii> ele, vertices, hor, lan;
unordered_map <ll, unordered_map <ll, bool> > vis, vis_vertices, vis_hor, vis_lan;

ll dx[4] = {-1, -1, 0, 0};
ll dy[4] = {-1, 0, -1, 0};

void fakeupdate (vi pos[], ll x, ll y){
    while (x<=lim){
        pos[x].pb(y);
        x += (x&(-x));
    }
}

void compress(vi pos[], vi BIT[]){
    for (ll i=1; i<=lim; i++){
        pos[i].pb(0);
        sort(pos[i].begin(), pos[i].end());
        pos[i].erase(unique(pos[i].begin(), pos[i].end()), pos[i].end());
        BIT[i].assign(pos[i].size(), 0);
    }
}

void update (vi pos[], vi BIT[], ll x, ll y){
    for (ll i = x; i<=lim; i+=(i&(-i))){
        BIT[i][lower_bound(pos[i].begin(), pos[i].end(), y)-pos[i].begin()]++;
    }
}

void fin (vi BIT[]){
    for (ll i=1; i<=lim; i++){
        for (int j=1; j<BIT[i].size(); j++) BIT[i][j]+=BIT[i][j-1];
    }
}

ll get (vi pos[], vi BIT[], ll x, ll y){
    ll ret = 0;
    for (ll i=x; i>0; i&=i-1){
        auto st = upper_bound(pos[i].begin(), pos[i].end(), y);
        st--;
        ret += BIT[i][st-pos[i].begin()];
    }
//    cerr<<"  "<<ret<<"\n";
    return ret;
}


void dfs (ll u, ll v, ll pos){
    if (!vis[u][v]){
        fakeupdate(pos_cnt, u, v);
        ele.pb({u, v});
        vis[u][v] = true;
        for (ll i=0; i<4; i++){
            ll x = u +dx[i], y = v+dy[i];
            if (x>=1 && y>=1 && x<=n && y<=m && !vis_vertices[x][y]){
//                cerr<<x<<" "<<y<<"\n";
                fakeupdate(pos_vertices, x, y);
                vertices.pb({x, y});
                vis_vertices[x][y] = true;
            }
        }
        for (ll i=-1; i<=0; i++){
            ll x = u+i, y = v;
            if (x>=1 && y>=1 && x<=n && y<=m && !vis_lan[x][y]){
                fakeupdate(pos_lan, x, y);
                lan.pb({x, y});
                vis_lan[x][y] = true;
            }
            x = u; y = v+i;
            if (x>=1 && y>=1 && x<=n && y<=m && !vis_hor[x][y]){
                fakeupdate(pos_hor, x, y);
                hor.pb({x, y});
                vis_hor[x][y] = true;
            }
        }
    }
    vis[u][v] = true;
    if (pos==len) return;
    if (s[pos]=='N') dfs(u-1, v, pos+1);
    else if (s[pos]=='S') dfs(u+1, v, pos+1);
    else if (s[pos]=='E') dfs(u, v+1, pos+1);
    else dfs(u, v-1, pos+1);
}


ll get_range (vi pos[], vi bit[], ll xl, ll yl, ll xr, ll yr){
    return get(pos, bit, xr, yr) - get(pos, bit, xl-1, yr) - get(pos, bit, xr, yl-1) + get(pos, bit,xl-1, yl-1);
}

void init(int _n, int _m, int _sx, int _sy, int _len, char *S) {
    n = _n;
    m = _m;
    sx = _sx;
    sy = _sy;
    len = _len;
    s = S;
    dfs (sx, sy, 0);
    compress(pos_vertices, bit_vertices);
    compress(pos_cnt, bit_cnt);
    compress(pos_hor, bit_hor);
    compress(pos_lan, bit_lan);
    //
    for (pii x:ele) update (pos_cnt, bit_cnt, x.fi, x.se);
    for (pii x:vertices) update (pos_vertices, bit_vertices, x.fi, x.se);
    for (pii x:hor) update (pos_hor, bit_hor, x.fi, x.se);
    for (pii x:lan) update (pos_lan, bit_lan, x.fi, x.se);
    //
    fin(bit_vertices);
    fin(bit_cnt);
    fin(bit_hor);
    fin(bit_lan);
}

int colour(int xl, int yl, int xr, int yr) {
    ll nodes = (xr>xl && yr>yl) ? get_range (pos_vertices, bit_vertices, xl, yl, xr-1, yr-1) : 0;
        ll edges = 0;
        if (xr>xl) edges+=get_range(pos_lan, bit_lan, xl, yl, xr-1, yr);
        if (yr>yl) edges+=get_range(pos_hor, bit_hor, xl, yl, xr, yr-1);
        ll tplt = 1;
//        nodes += 2*(xr-xl+yr-yl+2);
//        edges += 2*(xr-xl+yr-yl+2);
//        cerr<<"    "<<edges<<"  "<<nodes<<"  "<<tplt<<"\n";
        int cnttotal = get_range(pos_cnt, bit_cnt, xl, yl, xr, yr);
        int cntmid =0;
        if (xl+2<=xr && yl+2<=yr) cntmid = get_range(pos_cnt, bit_cnt, xl+1, yl+1, xr-1, yr-1);
        //
        if (cntmid==cnttotal && nodes>=1) tplt++;
        //
        ll tmp = edges-nodes+tplt-cnttotal;
        if (tmp<0) assert(0==1);
        return tmp;
}

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