| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1158350 | davele | Land of the Rainbow Gold (APIO17_rainbow) | C++20 | 0 ms | 0 KiB |
#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";
// }
//}