Submission #1158351

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158351		davele	Land of the Rainbow Gold (APIO17_rainbow)	C++20	50 / 100	1103 ms	247848 KiB

rainbow

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

#include <bits/stdc++.h>
#define ll long long
#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 = 250000, 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<=n){
        pos[x].pb(y);
        x += (x&(-x));
    }
}

void compress(vi pos[], vi BIT[]){
    for (ll i=1; i<=n; 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<=n; i+=(i&(-i))){
        for (ll j = lower_bound(pos[i].begin(), pos[i].end(), y)-pos[i].begin(); j<(ll)pos[i].size(); j+=(j&(-j))){
            BIT[i][j]++;
//            cerr<<j<<" "<<BIT[i].size()<<"\n";
        }
    }
}

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--;
        for (ll j = (st-pos[i].begin()); j>0; j&=j-1){
//            cerr<<j<<"\n";
//            cerr<<"g  "<<j<<" "<<BIT[i].size()<<" "<<BIT[i<<"\n";
            ret += BIT[i][j];
        }
    }
//    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);
}

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;
        if (nodes==(ll)vertices.size() && nodes>=1) tplt++;
//        nodes += 2*(xr-xl+yr-yl+2);
//        edges += 2*(xr-xl+yr-yl+2);
//        cerr<<"    "<<edges<<"  "<<nodes<<"  "<<tplt<<"\n";
        return edges-nodes+tplt-get_range(pos_cnt, bit_cnt, xl, yl, xr, yr);
}


//signed main(){
//    ios_base::sync_with_stdio(0);
//    cin.tie(0);
//    cout.tie(0);
//    //
////    freopen (".inp", "r", stdin);
////    freopen (".out", "w", stdout);
//    cin>>n>>m>>sx>>sy>>len>>s>>q;
//    //
//    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);
//    //
//    for (ll i=1; i<=q; i++){
//        ll xl, yl, xr, yr;
//        cin>>xl>>yl>>xr>>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;
//        if (nodes==(ll)vertices.size()) tplt++;
////        nodes += 2*(xr-xl+yr-yl+2);
////        edges += 2*(xr-xl+yr-yl+2);
////        cerr<<"    "<<edges<<"  "<<nodes<<"  "<<tplt<<"\n";
//        cout<<edges-nodes+tplt-get_range(pos_cnt, bit_cnt, xl, yl, xr, yr)<<"\n";
//    }
//}

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