Submission #383373

#	Time	Username	Problem	Language	Result	Execution time	Memory
383373		AriaH	Land of the Rainbow Gold (APIO17_rainbow)	C++11	12 / 100	1552 ms	218464 KiB

rainbow

/** I can do this all day **/
#include <bits/stdc++.h>
#include "rainbow.h"

#pragma GCC optimize("O2")
using namespace std;

typedef long long                   ll;
typedef long double                 ld;
typedef pair<int,int>               pii;
typedef pair<ll,ll>                 pll;
#define all(x)                      (x).begin(),(x).end()
#define F                           first
#define S                           second
#define Mp                          make_pair
#define SZ(x)			    		(int)x.size()
#define fast_io                     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io                     freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);

const int N = 2e5 + 10;
const ll mod = 1e9 + 7;
const ll mod2 = 998244353;
const ll inf = 8e18;
const int LOG = 22;

ll pw(ll a , ll b, ll M)  { return (!b ? 1 : (b & 1 ? (a * pw(a * a % M, b / 2, M)) % M : pw(a * a % M, b / 2, M))); }

struct segment
{
	segment () {}
	vector < int > seg[N << 2], id[N << 2];
	void add(int p, int x, int v = 1, int tl = 0, int tr = N - 1)
	{
		if(p > tr || p < tl) return;
		if(tl == tr)
		{
			seg[v].push_back(x);
			return;
		}
		int mid = (tl + tr) >> 1;
		add(p, x, v << 1, tl, mid);
		add(p, x, v << 1 | 1, mid + 1, tr);
	}
	void Merge(int v)
	{
		int n = SZ(seg[v << 1]), m = SZ(seg[v << 1 | 1]), i = 0, j = 0, k = 0;
		id[v].resize(n + m + 1, 0);
		seg[v].resize(n + m);
		while(j < n || k < m)
		{
			if(j < n && (k == m || seg[v << 1][j] < seg[v << 1 | 1][k]))
			{
				seg[v][i] = seg[v << 1][j];
				id[v][i + 1] = id[v][i] + 1;
				j ++;
			}
			else
			{
				seg[v][i] = seg[v << 1 | 1][k];
				id[v][i + 1] = id[v][i];
				k ++;
			}
			i ++;
		}
	}
	void build(int v = 1, int tl = 0, int tr = N - 1)
	{
		if(tl == tr)
		{
			sort(all(seg[v]));
			seg[v].resize(unique(all(seg[v])) - seg[v].begin());
			return;
		}
		int mid = (tl + tr) >> 1;
		build(v << 1, tl, mid);
		build(v << 1 | 1, mid + 1, tr);
		Merge(v);
	}
	int get(int l, int r, int x, int v = 1, int tl = 0, int tr = N - 1)
	{
		if(l > tr || r < tl || l > r) return 0;
		if(l <= tl && tr <= r)
		{
			return x;
		}
		int mid = (tl + tr) >> 1;
		return get(l, r, id[v][x], v << 1, tl, mid) + get(l, r, x - id[v][x], v << 1 | 1, mid + 1, tr);
	}
	int ask(int l, int r, int L, int R)
	{
		if(l > r || L > R) return 0;
		int x = upper_bound(all(seg[1]), R) - seg[1].begin();
		int x2 = upper_bound(all(seg[1]), L - 1) - seg[1].begin();
		return get(l, r, x) - get(l, r, x2);
	}
} S1, S2, S3, S4; /// S1 -> bala chap 2 * 2
				  /// S2 -> bala chap 1 * 2
				  /// S3 -> bala chap 2 * 1
				  /// S4 -> bala chap 1 * 1

map < pii, int > mp;

int mnR, mnC, mxR, mxC;

void init(int R, int C, int sr, int sc, int M, char *S)
{
	char* s = S;
	int a = sr, b = sc, n = M;
	vector < pii > points;
	mnR = mxR = a;
	mnC = mxC = b;
	points.push_back(Mp(a, b));
	for(int i = 0; i < n; i ++)
	{
		if(s[i] == 'N')
		{
			a --;
		}
		if(s[i] == 'S')
		{
			a ++;
		}
		if(s[i] == 'E')
		{
			b ++;
		}
		if(s[i] == 'W')
		{
			b --;
		}
		points.push_back(Mp(a, b));
	}
	for(auto x : points)
	{
		mp[x] = 1;
		mnR = min(mnR, x.F);
		mxR = max(mxR, x.F);
		mnC = min(mnC, x.S);
		mxC = max(mxC, x.S);
	}
	for(auto x : points)
	{
		if(mp.count(Mp(x.F + 1, x.S)) == 1 && mp.count(Mp(x.F + 1, x.S + 1)) == 1 && mp.count(Mp(x.F, x.S + 1)) == 1)
		{
			S1.add(x.F, x.S);
		}
		if(mp.count(Mp(x.F + 1, x.S)) == 1)
		{
			S2.add(x.F, x.S);
		}
		if(mp.count(Mp(x.F, x.S + 1)) == 1)
		{
			S3.add(x.F, x.S);
		}
		S4.add(x.F, x.S);
	}
	S1.build();
	S2.build();
	S3.build();
	S4.build();
}

int colour(int ar, int ac, int br, int bc)				/// V + F - M = 1 + C -> C = tedad moalefe haye graph mosatah
{									/// M - V + C + 1 = F -> toye soale ma F - 1 ro mikhaim C = 2 age doresh tohi bashe
	int r1 = ar, c1 = ac, r2 = br, c2 = bc;
	int V = 0, M = 0;
	V += S4.ask(r1, r2, c1, c2);
	M += S3.ask(r1, r2, c1, c2 - 1);
	M += S2.ask(r1, r2 - 1, c1, c2);
	M += S4.ask(r1, r2, c1, c1);
	M += S4.ask(r1, r2, c2, c2);
	M += S4.ask(r1, r1, c1, c2);
	M += S4.ask(r2, r2, c1, c2);
	int tot = M - V + 1, ret = 0;
	ret += S1.ask(r1, r2 - 1, c1, c2 - 1);
	ret += S2.ask(r1, r2 - 1, c1, c1);
	ret += S2.ask(r1, r2 - 1, c2, c2);
	ret += S3.ask(r1, r1, c1, c2 - 1);
	ret += S3.ask(r2, r2, c1, c2 - 1);
	ret += mp.count(Mp(r1, c1));
	ret += mp.count(Mp(r1, c2));
	ret += mp.count(Mp(r2, c1));
	ret += mp.count(Mp(r2, c2));
	if(mnR > r1 && mxR < r2 && mnC > c1 && mxC < c2) tot ++;
	return tot - ret;
}

/*int main()
{
    return 0;    
}
*/
/** test corner cases(n = 1?) watch for overflow or minus indices **/

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