oj.uz

Submission #554001

# Submission time Handle Problem Language Result Execution time Memory
554001 2022-04-27T14:22:13 Z hhhhaura Land of the Rainbow Gold (APIO17_rainbow) C++14
0 / 100
 437 ms 302376 KB 
#define wiwihorz
#include "rainbow.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse")
#pragma loop-opt(on)
#define rep(i, a, b) for(int i = a; i <= b; i ++)
#define rrep(i, a, b) for(int i = b; i >= a; i --)
#define all(x) x.begin(), x.end()
#define ceil(a, b) ((a + b - 1) / (b))
#define ll long long int
#define lld long double
#define pii pair<int, int>
#define random mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count())
#define INF 1000000000000000000
#define MOD 1000000007
#define eps (1e-9)
using namespace std;
#ifdef wiwihorz
#define print(a...)cerr<<"Line "<<__LINE__<<":",kout("["+string(#a)+"] = ", a)
void vprint(auto L,auto R){while(L<R)cerr<<*L<<" \n"[next(L) == R], ++L; }
void kout() { cerr << endl; }
template<class T1,class ... T2>void kout(T1 a,T2 ... e){cerr<<a<<" ",kout(e...);}
#else
#define print(...) 0
#define vprint(...) 0
#endif
#define x first
#define y second
namespace solver {
	int ii = 0, r, c;
	const int P = 10000000;
	struct node { int val, l, r; };
	vector<node> v(P, {0, 0, 0});
	vector<int> R, N, H, V;
	set<pii> vs, hs, nd, rv;
	int get_copy(int cur) {
		v[++ii] = v[cur];
		return ii;
	}
	void init_(int _r, int _c) {
		r = _r, c = _c;
		r++, c ++;
		R.assign(c + 1, 0);
		N.assign(c + 1, 0);
		H.assign(c + 1, 0);
		V.assign(r + 1, 0);
		R[0] = get_copy(0);
		N[0] = get_copy(0);
		H[0] = get_copy(0);
		V[0] = get_copy(0);
		vs.clear();
		hs.clear();
		nd.clear();
		rv.clear();
	}
	void modify(int L, int R, int pre, int cur, int id, int val) {
		if(L == R) v[cur].val += val;
		else {
			int mid = (L + R) / 2;
			if(id <= mid) {
				v[cur].l = get_copy(v[pre].l);
				modify(L, mid, v[pre].l, v[cur].l, id, val);
			}
			else {
				v[cur].r = get_copy(v[pre].r);
				modify(mid + 1, R, v[pre].r, v[cur].r, id, val);
			}
			v[cur].val = v[v[cur].l].val + v[v[cur].r].val;
		}

	}
	int query(int a, int b, int L, int R, int l, int r) {
		int mid = (L + R) / 2;
		if(r < L || l > R || (!a && !b)) return 0;
		if(l <= L && r >= R) return v[b].val - v[a].val;
		else return query(v[a].l, v[b].l, L, mid, l, r) + 
			query(v[a].r, v[b].r, mid + 1, R, l, r);
	}
	void add_position(int x, int y) {
		rv.insert({x, y});
		rep(i, 0, 1) rep(j, 0, 1) nd.insert({x + i, y + j});
		hs.insert({x + 1, y});
		hs.insert({x + 1, y + 1});
		vs.insert({y + 1, x});
		vs.insert({y + 1, x + 1});
	}
	void build_seg() {
		int pos = 0;
		for(auto i : rv) {
			rep(j, pos + 1, i.x) R[j] = get_copy(R[j - 1]);
			int cur = get_copy(R[i.x]);
			modify(1, c, R[i.x], cur, i.y, 1);
			R[i.x] = cur;
			pos = i.x;
		}
		rep(i, pos + 1, r) R[i] = get_copy(R[i - 1]);
		pos = 0;
		for(auto i : nd) {
			rep(j, pos + 1, i.x) N[j] = get_copy(N[j - 1]);
			int cur = get_copy(N[i.x]);
			modify(1, c, N[i.x], cur, i.y, 1);
			N[i.x] = cur;
			pos = i.x;
		}
		rep(i, pos + 1, r) N[i] = get_copy(N[i - 1]);
		pos = 0;
		for(auto i : hs) {
			rep(j, pos + 1, i.x) H[j] = get_copy(H[j - 1]);
			int cur = get_copy(H[i.x]);
			modify(1, c, H[i.x], cur, i.y, 1);
			H[i.x] = cur;
			pos = i.x;
		}
		rep(i, pos + 1, r) H[i] = get_copy(H[i - 1]);
		pos = 0;
		for(auto i : vs) {
			rep(j, pos + 1, i.x) V[j] = get_copy(V[j - 1]);
			int cur = get_copy(V[i.x]);
			modify(1, r, V[i.x], cur, i.y, 1);
			V[i.x] = cur;
			pos = i.x;
		}
		rep(i, pos + 1, c) V[i] = get_copy(V[i - 1]);
	}
};
using namespace solver;
void init(int r, int c, int sr, int sc, int M, char *S) {
	init_(r, c);
	int x = sr, y = sc;
	add_position(x, y);
	rep(i, 0, M - 1) {
		if(S[i] == 'W') y -= 1;
		else if(S[i] == 'E') y += 1;
		else if(S[i] == 'N') x -= 1;
		else x += 1;
		add_position(x, y);
	}
	build_seg();
	return;
}
int colour(int ar, int ac, int br, int bc) {
    int rr = query(R[ar - 1], R[br], 1, c, ac, bc);
	int vv = query(N[ar], N[br], 1, c, ac + 1, bc)
		+ (br - ar + 2) * 2 + (bc - ac + 2) * 2 - 4;
	int ee = query(H[ar], H[br + 1], 1, c, ac + 1, bc)
		+ query(V[ac], V[bc + 1], 1, r, ar + 1, br) 
		+ (br - ar + 1) * 2 + (bc - ac + 1) * 2;
	int yes = query(R[ar - 1], R[ar], 1, c, ac, bc) 
		+ query(R[br - 1], R[br], 1, c, ac, bc)
		+ query(R[ar - 1], R[br], 1, c, ac, ac)
		+ query(R[ar - 1], R[br], 1, c, bc, bc);
	int ans = ee - vv + 2 - bool(yes || !rr) - rr;
	return ans;
}

Compilation message

rainbow.cpp:6: warning: ignoring '#pragma loop ' [-Wunknown-pragmas]
    6 | #pragma loop-opt(on)
      | 
rainbow.cpp:21:13: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   21 | void vprint(auto L,auto R){while(L<R)cerr<<*L<<" \n"[next(L) == R], ++L; }
      |             ^~~~
rainbow.cpp:21:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   21 | void vprint(auto L,auto R){while(L<R)cerr<<*L<<" \n"[next(L) == R], ++L; }
      |                    ^~~~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 117704 KB Output is correct
2 Correct 54 ms 117876 KB Output is correct
3 Correct 51 ms 117708 KB Output is correct
4 Correct 54 ms 117772 KB Output is correct
5 Correct 58 ms 117988 KB Output is correct
6 Correct 52 ms 117704 KB Output is correct
7 Correct 53 ms 117708 KB Output is correct
8 Correct 53 ms 117700 KB Output is correct
9 Runtime error 158 ms 238420 KB Execution killed with signal 6
10 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 117708 KB Output is correct
2 Correct 56 ms 117604 KB Output is correct
3 Runtime error 301 ms 277684 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 117640 KB Output is correct
2 Runtime error 437 ms 302376 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 117704 KB Output is correct
2 Correct 54 ms 117876 KB Output is correct
3 Correct 51 ms 117708 KB Output is correct
4 Correct 54 ms 117772 KB Output is correct
5 Correct 58 ms 117988 KB Output is correct
6 Correct 52 ms 117704 KB Output is correct
7 Correct 53 ms 117708 KB Output is correct
8 Correct 53 ms 117700 KB Output is correct
9 Runtime error 158 ms 238420 KB Execution killed with signal 6
10 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 117704 KB Output is correct
2 Correct 54 ms 117876 KB Output is correct
3 Correct 51 ms 117708 KB Output is correct
4 Correct 54 ms 117772 KB Output is correct
5 Correct 58 ms 117988 KB Output is correct
6 Correct 52 ms 117704 KB Output is correct
7 Correct 53 ms 117708 KB Output is correct
8 Correct 53 ms 117700 KB Output is correct
9 Runtime error 158 ms 238420 KB Execution killed with signal 6
10 Halted 0 ms 0 KB -