Submission #1133127

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133127		Math4Life2020	Land of the Rainbow Gold (APIO17_rainbow)	C++20	50 / 100	3102 ms	790664 KiB

rainbow

#include "rainbow.h"
#include <bits/stdc++.h>
#include <cmath>
using namespace std;
using ll = int; using pii = pair<ll,ll>;
const ll INF = 1e9;

vector<pii> vv; //snake vertices 
vector<pii> vev,veh; //snake edges
//vev: (x,y) -> (x+1,y)
//veh: (x,y) -> (x,y+1)
vector<pii> vf; //snake ~internal faces
ll xsmin = INF; ll ysmin = INF; ll xsmax = -1; ll ysmax = -1;

inline ll v2(ll x) {
    return __builtin_ctz(x);
}

const ll Nm = 524288; const ll Es = 19;

map<ll,ll> mv[2*Nm];
void prcV(vector<pii> v0) {
    sort(v0.begin(),v0.end());
    vector<ll> mv0;
    for (ll t=0;t<(2*Nm);t++) {
        mv[t][-1]=0;
        mv0.push_back(0);
    }
    for (pii p0: v0) {
        ll x = p0.first; ll y = p0.second;
        ll p = y+Nm;
        do {
            mv0[p]++;
            mv[p][x]=mv0[p];
            p=p/2;
        } while (p>0);
    }
}

ll qryV(ll x, ll y) {
    ll ans = 0;
    while (y>=0) {
        ll vy = v2(y+1);
        ll p = (y>>vy)+(1<<(Es-vy));
        ans += (*(--mv[p].upper_bound(x))).second;
        y -= (1<<vy);
    }
    return ans;
}

vector<pii> clr(vector<pii> v0) {
	sort(v0.begin(),v0.end());
	v0.erase(unique(v0.begin(),v0.end()),v0.end());
	vector<pii> v1;
	for (pii p0: v0) {
		if (p0.first>=0 && p0.second>=0) {
			v1.push_back(p0);
		}
	}
	return v1;
}

map<ll,ll> mev[2*Nm];
void prcEV(vector<pii> v0) {
    sort(v0.begin(),v0.end());
    vector<ll> mv0;
    for (ll t=0;t<(2*Nm);t++) {
        mev[t][-1]=0;
        mv0.push_back(0);
    }
    for (pii p0: v0) {
        ll x = p0.first; ll y = p0.second;
        ll p = y+Nm;
        do {
            mv0[p]++;
            mev[p][x]=mv0[p];
            p=p/2;
        } while (p>0);
    }
}

ll qryEV(ll x, ll y) {
    ll ans = 0;
    while (y>=0) {
        ll vy = v2(y+1);
        ll p = (y>>vy)+(1<<(Es-vy));
        ans += (*(--mev[p].upper_bound(x))).second;
        y -= (1<<vy);
    }
    return ans;
}

map<ll,ll> meh[2*Nm];
void prcEH(vector<pii> v0) {
    sort(v0.begin(),v0.end());
    vector<ll> mv0;
    for (ll t=0;t<(2*Nm);t++) {
        meh[t][-1]=0;
        mv0.push_back(0);
    }
    for (pii p0: v0) {
        ll x = p0.first; ll y = p0.second;
        ll p = y+Nm;
        do {
            mv0[p]++;
            meh[p][x]=mv0[p];
            p=p/2;
        } while (p>0);
    }
}

ll qryEH(ll x, ll y) {
    ll ans = 0;
    while (y>=0) {
        ll vy = v2(y+1);
        ll p = (y>>vy)+(1<<(Es-vy));
        ans += (*(--meh[p].upper_bound(x))).second;
        y -= (1<<vy);
    }
    return ans;
}

map<ll,ll> mf[2*Nm];
void prcF(vector<pii> v0) {
    sort(v0.begin(),v0.end());
    vector<ll> mv0;
    for (ll t=0;t<(2*Nm);t++) {
        mf[t][-1]=0;
        mv0.push_back(0);
    }
    for (pii p0: v0) {
        ll x = p0.first; ll y = p0.second;
        ll p = y+Nm;
        do {
            mv0[p]++;
            mf[p][x]=mv0[p];
            p=p/2;
        } while (p>0);
    }
}

ll qryF(ll x, ll y) {
    ll ans = 0;
    while (y>=0) {
        ll vy = v2(y+1);
        ll p = (y>>vy)+(1<<(Es-vy));
        ans += (*(--mf[p].upper_bound(x))).second;
        y -= (1<<vy);
    }
    return ans;
}


void init(ll R, ll C, ll sr, ll sc, ll M, char* S) {
	sr--; sc--;
	vv.clear(); vev.clear(); veh.clear(); vf.clear();
	ll x = sr; ll y = sc;
	vv.push_back({x,y});
	for (ll t=0;t<M;t++) {
		if (S[t]=='N') {
			x--;
		}
		if (S[t]=='S') {
			x++;
		}
		if (S[t]=='E') {
			y++;
		}
		if (S[t]=='W') {
			y--;
		}
		vv.push_back({x,y});
	}
	for (pii p0: vv) {
		ll x1 = p0.first; ll y1 = p0.second;
		vev.push_back({x1,y1});
		vev.push_back({x1-1,y1});
		veh.push_back({x1,y1});
		veh.push_back({x1,y1-1});
		vf.push_back({x1,y1});
		vf.push_back({x1-1,y1});
		vf.push_back({x1,y1-1});
		vf.push_back({x1-1,y1-1});
	}
	vv = clr(vv); //remove duplicates / negatives
	vev = clr(vev);
	veh = clr(veh);
	vf = clr(vf);
	for (pii p0: vv) {
		xsmin = min(xsmin, p0.first);
		ysmin = min(ysmin, p0.second);
		xsmax = max(xsmax, p0.first);
		ysmax = max(ysmax, p0.second);
	}
    prcV(vv);
	prcEH(veh);
	prcEV(vev);
	prcF(vf);
}

int colour(ll ar, ll ac, ll br, ll bc) {
	ar--; ac--; br--; bc--;
	long long V = (long long)(br-ar+1)*(bc-ac+1);
	long long E = (long long)(br-ar)*(bc-ac+1)+(br-ar+1)*(bc-ac);
	long long F = (long long)(br-ar)*(bc-ac); //INTERNAL faces
	if (ar<xsmin && ac<ysmin && br>xsmax && bc>ysmax) {
		F++;
	} 
	//cout << "V,E,F init="<<V<<","<<E<<","<<F<<"\n";
    //turn the below into dynamic segtree stuff
	// for (pii p0: vv) {
	// 	ll x = p0.first; ll y = p0.second;
	// 	if (x>=ar && x<=br && y>=ac && y<=bc) {
	// 		V--;
	// 	}
	// }
	// for (pii p0: vev) {
	// 	ll x = p0.first; ll y = p0.second;
	// 	if (x>=ar && x<br && y>=ac && y<=bc) { //x<br strict
	// 		E--;
	// 	}
	// }
	// for (pii p0: veh) {
	// 	ll x = p0.first; ll y = p0.second;
	// 	if (x>=ar && x<=br && y>=ac && y<bc) { //y<bc strict
	// 		E--;
	// 	}
	// }
	// for (pii p0: vf) {
	// 	ll x = p0.first; ll y = p0.second;
	// 	if (x>=ar && x<br && y>=ac && y<bc) { //x<br,y<bc strict
	// 		F--;
	// 	}
	// }
	V -= (qryV(br,bc)+qryV(ar-1,ac-1)-qryV(br,ac-1)-qryV(ar-1,bc));
	E -= (qryEV(br-1,bc)+qryEV(ar-1,ac-1)-qryEV(br-1,ac-1)-qryEV(ar-1,bc));
	E -= (qryEH(br,bc-1)+qryEH(ar-1,ac-1)-qryEH(br,ac-1)-qryEH(ar-1,bc-1));
	F -= (qryF(br-1,bc-1)+qryF(ar-1,ac-1)-qryF(br-1,ac-1)-qryF(ar-1,bc-1));
	//cout << "V,E,F final="<<V<<","<<E<<","<<F<<"\n";
	return (F+V-E);
}

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