| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1272712 | SoMotThanhXuan | Land of the Rainbow Gold (APIO17_rainbow) | C++20 | 0 ms | 0 KiB |
#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define FOR(i, a, b) for(int i = (a), _b = (b); i <= _b; ++i)
#define REP(i, a, b) for(int i = (a), _b = (b); i >= _b; --i)
#define mp make_pair
#define all(v) v.begin(), v.end()
#define uni(v) v.erase(unique(all(v)), v.end())
#define Bit(x, i) ((x >> (i)) & 1)
#define Mask(i) (1 << (i))
#define Cnt(x) __builtin_popcount(x)
#define Cntll(x) __builtin_popcountll(x)
#define Ctz(x) __builtin_ctz(x)
#define Ctzll(x) __builtin_ctzll(x)
#define Clz(x) __builtin_clz(x)
#define Clzll(x) __builtin_clzll(x)
inline bool maximize(int &u, int v){ return v > u ? u = v, true : false; }
inline bool minimize(int &u, int v){ return v < u ? u = v, true : false; }
inline bool maximizell(long long &u, long long v){ return v > u ? u = v, true : false; }
inline bool minimizell(long long &u, long long v){ return v < u ? u = v, true : false; }
const int mod = 1e9 + 7;
inline int fastPow(int a, int n){
if(n == 0) return 1;
int t = fastPow(a, n >> 1);
t = 1ll * t * t % mod;
if(n & 1) t = 1ll * t * a % mod;
return t;
}
inline void add(int &u, int v){ u += v; if(u >= mod) u -= mod; }
inline void sub(int &u, int v){ u -= v; if(u < 0) u += mod; }
const int maxN = 1e5 + 5;
const int logN = __lg(maxN);
const int maxNlogN = maxN * (logN + 2);
const int inf = 1e9;
const long long infll = 1e18;
bool cmp(const pair<int, int> &a, const pair<int, int> &b) {return a.first > b.first; }
struct Node{
int lc, rc, sum;
Node(){
lc = rc = sum = 0;
}
}it[4][maxNlogN];
int numNode[4];
int rootVersion[4][maxN];
void update(int pre, int cur, int l, int r, int p, int type){
if(l == r){
it[type][cur].sum = it[type][pre].sum + 1;
return;
}
int mid = l + r >> 1;
if(p <= mid){
it[type][cur].rc = it[type][pre].rc;
it[type][cur].lc = ++numNode[type];
update(it[type][pre].lc, it[type][cur].lc, l, mid, p, type);
}else{
it[type][cur].rc = ++numNode[type];
it[type][cur].lc = it[type][pre].lc;
update(it[type][pre].rc, it[type][cur].rc, mid + 1, r, p, type);
}
it[type][cur].sum = it[type][it[type][cur].lc].sum + it[type][it[type][cur].rc].sum;
}
int get(int curl, int curr, int l, int r, int u, int v, int type){
if(l >= u && r <= v) return it[type][curr].sum - it[type][curl].sum;
int mid = l + r >> 1;
if(v <= mid) return get(it[type][curl].lc, it[type][curr].lc, l, mid, u, v, type);
if(u > mid) return get(it[type][curl].rc, it[type][curr].rc, mid + 1, r, u, v, type);
return get(it[type][curl].lc, it[type][curr].lc, l, mid, u, v, type) + get(it[type][curl].rc, it[type][curr].rc, mid + 1, r, u, v, type);
}
bool visited[4][maxN];
int numRow, numCol;
vector<int> query[4][maxN];
int getVir(int u, int v, int x, int y){
return get(rootVersion[0][u - 1], rootVersion[0][v], 1, numRow, x, y, 0);
}
int getHor(int u, int v, int x, int y){
return get(rootVersion[1][u - 1], rootVersion[1][v], 1, numRow, x, y, 1);
}
int getRivers(int u, int v, int x, int y){
return get(rootVersion[2][u - 1], rootVersion[2][v], 1, numRow, x, y, 2);
}
int getVertexs(int u, int v, int x, int y){
return get(rootVersion[3][u - 1], rootVersion[3][v], 1, numRow, x, y, 3);
}
int colours(int ar, int ac, int br, int bc){
int V = getVertexs(ac, bc + 1, ar, br + 1);
// cout << "V " << V << '\n';
V += 2 * (bc + br - ac - ar) + 4;
int VertexsOnSide = getVertexs(ac, bc + 1, ar, ar) + getVertexs(ac, bc + 1, br + 1, br + 1);
if(ar < br) VertexsOnSide += getVertexs(ac, ac, ar + 1, br) + getVertexs(bc + 1, bc + 1, ar + 1, br);
V -= VertexsOnSide;
int E = getVir(ac, bc + 1, ar, br) + getHor(ac, bc, ar, br + 1);
// cout << "E " << E << '\n';
E += 2 * (bc + br - ac - ar + 2);
int EdgesOnSide = getHor(ac, bc, ar, ar) + getHor(ac, bc, br + 1, br + 1) + getVir(ac, ac, ar, br) + getVir(bc + 1, bc + 1, ar, br);
E -= EdgesOnSide;
int R = getRivers(ac, bc, ar, br);
// cout << V << ' ' << E << ' ' << R << ' ' << VertexsOnSide << ' ' << EdgesOnSide << '\n';
return E - V + 1 - R + (VertexsOnSide == 0);
}
void init(int R, int C, int sr, int sc, int M, string S){
numRow = R, numCol = C;
numRow += 2;
++numCol;
vector<pair<int, int>> rivers;
rivers.emplace_back(sr, sc);
for(char c : S){
if(c == 'N')--sr;
else if(c == 'S')++sr;
else if(c == 'E')++sc;
else --sc;
rivers.emplace_back(sr, sc);
}
sort(all(rivers));
uni(rivers);
for(auto[u, v] : rivers){
query[0][v].emplace_back(u);
query[0][v + 1].emplace_back(u);
query[1][v].emplace_back(u);
query[1][v].emplace_back(u + 1);
query[2][v].emplace_back(u);
query[3][v].emplace_back(u);
query[3][v].emplace_back(u + 1);
query[3][v + 1].emplace_back(u);
query[3][v + 1].emplace_back(u + 1);
}
FOR(v, 1, numCol){
FOR(type, 0, 3){
query[type][v].emplace_back(numRow);
sort(all(query[type][v]));
uni(query[type][v]);
for(int u : query[type][v]){
int preVersion = visited[type][v] ? rootVersion[type][v] : rootVersion[type][v - 1];
visited[type][v] = true;
rootVersion[type][v] = ++numNode[type];
update(preVersion, rootVersion[type][v], 1, numRow, u, type);
}
}
}
}
//void process(){
// int numRow, numCol, sr, sc, M;
// string S;
// cin >> numRow >> numCol >> sr >> sc >> M >> S;
// init(numRow, numCol, sr, sc, M, S);
// int q;
// cin >> q;
// while(q--){
// int ar, ac, br, bc;
// cin >> ar >> ac >> br >> bc;
// cout << colours(ar, ac, br, bc) << '\n';
// }
//}
//
//*
//6 4 3 3 9
//NWESSWEWS
//4
//2 3 2 3
//3 2 4 4
//5 3 6 4
//1 2 5 3
//*/
//#define LOVE "code"
//int main(){
// if(fopen(LOVE".inp", "r")){
// freopen(LOVE".inp", "r", stdin);
//// freopen(LOVE".out", "w", stdout);
// }
// ios_base::sync_with_stdio(false);
// cin.tie(0);
// cout.tie(0);
//
// int t = 1;
//// cin >> t;
// while(t--)
// process();
//// cerr << '\n' << "Time elapsed: " << (1.0 * clock() / CLOCKS_PER_SEC) << " s\n" ;
// return 0;
//}