oj.uz

Submission #80307

# Submission time Handle Problem Language Result Execution time Memory
80307 2018-10-20T00:05:05 Z qkxwsm Land of the Rainbow Gold (APIO17_rainbow) C++14
35 / 100
 3000 ms 273296 KB 
#include "rainbow.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/rope>

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;

random_device(rd);
mt19937 rng(rd());
const long long FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();

struct custom_hash
{
	template<class T>
    unsigned long long operator()(T v) const
	{
		unsigned long long x = v;
		x += FIXED_RANDOM; x += 11400714819323198485ull;
        x = (x ^ (x >> 30)) * 13787848793156543929ull;
        x = (x ^ (x >> 27)) * 10723151780598845931ull;
        return x ^ (x >> 31);
    }
};

template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T, class U> using hash_table = gp_hash_table<T, U, custom_hash>;

template<class T>
void ckmin(T &a, T b)
{
	a = min(a, b);
}
template<class T>
void ckmax(T &a, T b)
{
	a = max(a, b);
}
long long expo(long long a, long long e, long long mod)
{
	return ((e == 0) ? 1 : ((expo(a * a % mod, e >> 1, mod)) * ((e & 1) ? a : 1) % mod));
}
template<class T, class U>
T nmod(T &x, U mod)
{
	if (x >= mod) x -= mod;
}
template<class T>
T gcd(T a, T b)
{
	return (b ? gcd(b, a % b) : a);
}
template<class T>
T randomize(T mod)
{
	return (uniform_int_distribution<T>(0, mod - 1))(rng);
}

#define y0 ___y0
#define y1 ___y1
#define MP make_pair
#define MT make_tuple
#define PB push_back
#define PF push_front
#define fi first
#define se second
#define debug(x) cerr << #x << " = " << x << endl;
#define sz(x) ((int) (x.size()))

const long double PI = 4.0 * atan(1.0);
const long double EPS = 1e-9;

#define MAGIC 347
#define SINF 10007
#define CO 1000007
#define INF 1000000007
#define BIG 1000000931
#define LARGE 1696969696967ll
#define GIANT 2564008813937411ll
#define LLINF 2696969696969696969ll
#define MAXN 400013

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pdd;

int N;

struct pseg
{
	struct node
	{
		node *ch[2];
		ll stor;
		node()
		{
			ch[0] = ch[1] = nullptr;
			stor = 0;
		}
	};
	int T;
	node *root[MAXN];
	int ft[MAXN];
	vector<pair<ll, int> > updates[MAXN];
	ll DNE = 0;
	ll comb(ll a, ll b)
	{
		return a + b;
	}
	node* build(int L, int R)
	{
		node* t = new node();
		if (L == R) return t;
		int mid = (L + R) >> 1;
		t -> ch[0] = build(L, mid);
		t -> ch[1] = build(mid + 1, R);
		return t;
	}
	node *update(node *w, int L, int R, int a, ll v)
	{
		if (a < L || R < a)
		{
			return w;
		}
		node *t = new node();
		if (L == R)
		{
			t -> stor = w -> stor + v;
			return t;
		}
		int mid = (L + R) >> 1;
		t -> ch[0] = update(w -> ch[0], L, mid, a, v);
		t -> ch[1] = update(w -> ch[1], mid + 1, R, a, v);
		t -> stor = comb(t -> ch[0] -> stor, t -> ch[1] -> stor);
		return t;
	}
	ll query(node *w, int L, int R, int a, int b)
	{
		if (b < L || R < a)
		{
			return DNE;
		}
		if (a <= L && R <= b)
		{
			return w -> stor;
		}
		int mid = (L + R) >> 1;
		return query(w -> ch[0], L, mid, a, b) + query(w -> ch[1], mid + 1, R, a, b);
	}
	void process()
	{
		root[0] = build(0, N);
		ft[0] = 0;
		for (int i = 1; i <= N; i++)
		{
			for (auto p : updates[i])
			{
				ll v = p.fi; int idx = p.se;
				T++; root[T] = update(root[T - 1], 0, N, idx, v);
			}
			ft[i] = T;
		}
	}
	ll sum(int t, int L, int R)
	{
		return query(root[ft[t]], 0, N, L, R);
	}
	ll rect(int x0, int x1, int y0, int y1)
	{
		if (x0 > x1 || y0 > y1) return 0;
		return query(root[ft[x1]], 0, N, y0, y1) - query(root[ft[x0 - 1]], 0, N, y0, y1);
	}
};

pseg tseg, fseg, hseg, vseg, dseg, useg;
set<pii> s;
vector<pii> pts, face, hor, vert, dn, up;

void prep()
{
	for (pii p : s)
	{
		int x = p.fi, y = p.se;
		bool go[2][2];
		for (int i = 0; i < 2; i++)
		{
			for (int j = 0; j < 2; j++)
			{
				go[i][j] = true;
				if (s.find({x + i, y + j}) == s.end()) go[i][j] = false;
			}
		}
		pts.PB({x, y});
		if (go[0][1] && go[1][0] && go[1][1]) face.PB({x, y});
		if (go[1][0]) vert.PB({x, y});
		if (go[0][1]) hor.PB({x, y});
		if (go[1][1] && !go[0][1] && !go[1][0]) dn.PB({x, y});
		if (s.find({x - 1, y + 1}) != s.end() && s.find({x - 1, y}) == s.end() && !go[0][1]) up.PB({x, y});
 	}
	for (pii p : pts) tseg.updates[p.fi].PB({1, p.se}); tseg.process();
	for (pii p : face) fseg.updates[p.fi].PB({1, p.se}); fseg.process();
	for (pii p : hor) hseg.updates[p.fi].PB({1, p.se}); hseg.process();
	for (pii p : vert) vseg.updates[p.fi].PB({1, p.se}); vseg.process();
	for (pii p : dn) dseg.updates[p.fi].PB({1, p.se}); dseg.process();
	for (pii p : up) useg.updates[p.fi].PB({1, p.se}); useg.process();
}
void init(int R, int C, int x, int y, int K, char *S)
{
	N = max(R, C) + 2;
	s.insert({x, y});
	for (int i = 0; i < K; i++)
	{
		if (S[i] == 'N') x--;
		if (S[i] == 'S') x++;
		if (S[i] == 'E') y++;
		if (S[i] == 'W') y--;
		s.insert({x, y});
	}
	prep();
}

ll x0, x1, y0, y1;

ll edges()
{
	ll res = 0;
	res += vseg.rect(x0, x1 - 1, y0, y1) + (x1 - x0 + 2) * 2 + tseg.rect(x0, x0, y0, y1) + tseg.rect(x1, x1, y0, y1);
	// cerr << "alive\n";
	res += hseg.rect(x0, x1, y0, y1 - 1) + (y1 - y0 + 2) * 2 + tseg.rect(x0, x1, y0, y0) + tseg.rect(x0, x1, y1, y1);
	res += dseg.rect(x0, x1 - 1, y0, y1 - 1) + useg.rect(x0 + 1, x1, y0, y1 - 1);
	// cerr << "edges " << res << endl;
	return res;
}
ll vertices()
{
	ll res = 0;
	res = tseg.rect(x0, x1, y0, y1) + (x1 - x0 + 2) * 2 + (y1 - y0 + 2) * 2;
	// cerr << "vertices " << res << endl;
	return res;
}
ll faces()
{
	ll res = 0;
	res = fseg.rect(x0, x1 - 1, y0, y1 - 1);
	for (int i = x0; i < x1; i++)
	{
		if (s.find({i, y0}) != s.end() && s.find({i + 1, y0}) != s.end()) res++;
		if (s.find({i, y1}) != s.end() && s.find({i + 1, y1}) != s.end()) res++;
	}
	for (int i = y0; i < y1; i++)
	{
		if (s.find({x0, i}) != s.end() && s.find({x0, i + 1}) != s.end()) res++;
		if (s.find({x1, i}) != s.end() && s.find({x1, i + 1}) != s.end()) res++;
	}
	if (s.find({x0, y0}) != s.end()) res++;
	if (s.find({x1, y0}) != s.end()) res++;
	if (s.find({x0, y1}) != s.end()) res++;
	if (s.find({x1, y1}) != s.end()) res++;
	// cerr << "faces " << res << endl;
	return res;
}
int colour(int _x0, int _y0, int _x1, int _y1)
{
	x0 = _x0; x1 = _x1; y0 = _y0; y1 = _y1;
	if (tseg.rect(x0, x1, y0, y1) == 0) return 1;
	ll ans = tseg.rect(x0, x1, y0, y1) - tseg.rect(x0 + 1, x1 - 1, y0 + 1, y1 - 1);
	ans = (ans ? 1 : 0);
	// cerr << "bads " << ans << endl;
	// debug(edges()); debug(vertices()); debug(faces()); debug(ans);
	// cerr << "ans = " << ans << endl;
	ans = edges() - vertices() - faces() + 2 - ans;
    return ans;
}

Compilation message

rainbow.cpp: In function 'void prep()':
rainbow.cpp:204:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for (pii p : pts) tseg.updates[p.fi].PB({1, p.se}); tseg.process();
  ^~~
rainbow.cpp:204:54: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  for (pii p : pts) tseg.updates[p.fi].PB({1, p.se}); tseg.process();
                                                      ^~~~
rainbow.cpp:205:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for (pii p : face) fseg.updates[p.fi].PB({1, p.se}); fseg.process();
  ^~~
rainbow.cpp:205:55: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  for (pii p : face) fseg.updates[p.fi].PB({1, p.se}); fseg.process();
                                                       ^~~~
rainbow.cpp:206:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for (pii p : hor) hseg.updates[p.fi].PB({1, p.se}); hseg.process();
  ^~~
rainbow.cpp:206:54: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  for (pii p : hor) hseg.updates[p.fi].PB({1, p.se}); hseg.process();
                                                      ^~~~
rainbow.cpp:207:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for (pii p : vert) vseg.updates[p.fi].PB({1, p.se}); vseg.process();
  ^~~
rainbow.cpp:207:55: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  for (pii p : vert) vseg.updates[p.fi].PB({1, p.se}); vseg.process();
                                                       ^~~~
rainbow.cpp:208:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for (pii p : dn) dseg.updates[p.fi].PB({1, p.se}); dseg.process();
  ^~~
rainbow.cpp:208:53: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  for (pii p : dn) dseg.updates[p.fi].PB({1, p.se}); dseg.process();
                                                     ^~~~
rainbow.cpp:209:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for (pii p : up) useg.updates[p.fi].PB({1, p.se}); useg.process();
  ^~~
rainbow.cpp:209:53: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  for (pii p : up) useg.updates[p.fi].PB({1, p.se}); useg.process();
                                                     ^~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 56952 KB Output is correct
2 Correct 64 ms 57592 KB Output is correct
3 Correct 57 ms 57592 KB Output is correct
4 Correct 57 ms 57592 KB Output is correct
5 Correct 64 ms 58240 KB Output is correct
6 Correct 51 ms 58240 KB Output is correct
7 Correct 53 ms 58240 KB Output is correct
8 Correct 53 ms 58240 KB Output is correct
9 Correct 53 ms 58240 KB Output is correct
10 Correct 52 ms 58240 KB Output is correct
11 Correct 64 ms 58240 KB Output is correct
12 Correct 65 ms 58240 KB Output is correct
13 Correct 73 ms 58296 KB Output is correct
14 Correct 102 ms 58896 KB Output is correct
15 Correct 57 ms 58896 KB Output is correct
16 Correct 54 ms 58896 KB Output is correct
17 Correct 53 ms 58896 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 58896 KB Output is correct
2 Correct 53 ms 58896 KB Output is correct
3 Execution timed out 3052 ms 214012 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 58896 KB Output is correct
2 Correct 590 ms 265844 KB Output is correct
3 Correct 553 ms 271052 KB Output is correct
4 Correct 549 ms 271052 KB Output is correct
5 Correct 557 ms 271052 KB Output is correct
6 Correct 304 ms 271052 KB Output is correct
7 Correct 497 ms 271052 KB Output is correct
8 Correct 322 ms 271052 KB Output is correct
9 Correct 317 ms 271052 KB Output is correct
10 Correct 276 ms 271052 KB Output is correct
11 Correct 287 ms 271052 KB Output is correct
12 Correct 545 ms 271052 KB Output is correct
13 Correct 526 ms 272028 KB Output is correct
14 Correct 540 ms 272028 KB Output is correct
15 Correct 448 ms 272028 KB Output is correct
16 Correct 305 ms 272028 KB Output is correct
17 Correct 463 ms 272028 KB Output is correct
18 Correct 487 ms 272028 KB Output is correct
19 Correct 542 ms 272028 KB Output is correct
20 Correct 613 ms 272028 KB Output is correct
21 Correct 375 ms 272028 KB Output is correct
22 Correct 335 ms 272028 KB Output is correct
23 Correct 228 ms 272028 KB Output is correct
24 Correct 290 ms 272028 KB Output is correct
25 Correct 646 ms 272028 KB Output is correct
26 Correct 619 ms 273296 KB Output is correct
27 Correct 685 ms 273296 KB Output is correct
28 Correct 515 ms 273296 KB Output is correct
29 Correct 320 ms 273296 KB Output is correct
30 Correct 461 ms 273296 KB Output is correct
31 Correct 570 ms 273296 KB Output is correct
32 Correct 579 ms 273296 KB Output is correct
33 Correct 642 ms 273296 KB Output is correct

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 56952 KB Output is correct
2 Correct 64 ms 57592 KB Output is correct
3 Correct 57 ms 57592 KB Output is correct
4 Correct 57 ms 57592 KB Output is correct
5 Correct 64 ms 58240 KB Output is correct
6 Correct 51 ms 58240 KB Output is correct
7 Correct 53 ms 58240 KB Output is correct
8 Correct 53 ms 58240 KB Output is correct
9 Correct 53 ms 58240 KB Output is correct
10 Correct 52 ms 58240 KB Output is correct
11 Correct 64 ms 58240 KB Output is correct
12 Correct 65 ms 58240 KB Output is correct
13 Correct 73 ms 58296 KB Output is correct
14 Correct 102 ms 58896 KB Output is correct
15 Correct 57 ms 58896 KB Output is correct
16 Correct 54 ms 58896 KB Output is correct
17 Correct 53 ms 58896 KB Output is correct
18 Execution timed out 3025 ms 273296 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 56952 KB Output is correct
2 Correct 64 ms 57592 KB Output is correct
3 Correct 57 ms 57592 KB Output is correct
4 Correct 57 ms 57592 KB Output is correct
5 Correct 64 ms 58240 KB Output is correct
6 Correct 51 ms 58240 KB Output is correct
7 Correct 53 ms 58240 KB Output is correct
8 Correct 53 ms 58240 KB Output is correct
9 Correct 53 ms 58240 KB Output is correct
10 Correct 52 ms 58240 KB Output is correct
11 Correct 64 ms 58240 KB Output is correct
12 Correct 65 ms 58240 KB Output is correct
13 Correct 73 ms 58296 KB Output is correct
14 Correct 102 ms 58896 KB Output is correct
15 Correct 57 ms 58896 KB Output is correct
16 Correct 54 ms 58896 KB Output is correct
17 Correct 53 ms 58896 KB Output is correct
18 Execution timed out 3025 ms 273296 KB Time limit exceeded
19 Halted 0 ms 0 KB -