oj.uz

Submission #554005

# Submission time Handle Problem Language Result Execution time Memory
554005 2022-04-27T14:28:19 Z hhhhaura Land of the Rainbow Gold (APIO17_rainbow) C++14
38 / 100
 3000 ms 126136 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 = 8000000;
	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];
		if(ii >= P) while(1);
		return ii;
	}
	void init_(int _r, int _c) {
		r = _r, c = _c;
		r+= 2, c += 2;
		R.assign(r + 1, 0);
		N.assign(r + 1, 0);
		H.assign(r + 1, 0);
		V.assign(c + 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
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 94156 KB Output is correct
2 Correct 45 ms 94424 KB Output is correct
3 Correct 43 ms 94356 KB Output is correct
4 Correct 43 ms 94304 KB Output is correct
5 Correct 48 ms 94452 KB Output is correct
6 Correct 43 ms 94152 KB Output is correct
7 Correct 43 ms 94224 KB Output is correct
8 Correct 43 ms 94200 KB Output is correct
9 Correct 43 ms 94228 KB Output is correct
10 Correct 42 ms 94156 KB Output is correct
11 Correct 44 ms 94284 KB Output is correct
12 Correct 44 ms 94312 KB Output is correct
13 Correct 47 ms 94604 KB Output is correct
14 Correct 49 ms 94692 KB Output is correct
15 Correct 42 ms 94112 KB Output is correct
16 Correct 43 ms 94176 KB Output is correct
17 Correct 42 ms 94156 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 94176 KB Output is correct
2 Correct 42 ms 94156 KB Output is correct
3 Correct 359 ms 115148 KB Output is correct
4 Execution timed out 3080 ms 123480 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 94112 KB Output is correct
2 Execution timed out 3082 ms 125516 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 94156 KB Output is correct
2 Correct 45 ms 94424 KB Output is correct
3 Correct 43 ms 94356 KB Output is correct
4 Correct 43 ms 94304 KB Output is correct
5 Correct 48 ms 94452 KB Output is correct
6 Correct 43 ms 94152 KB Output is correct
7 Correct 43 ms 94224 KB Output is correct
8 Correct 43 ms 94200 KB Output is correct
9 Correct 43 ms 94228 KB Output is correct
10 Correct 42 ms 94156 KB Output is correct
11 Correct 44 ms 94284 KB Output is correct
12 Correct 44 ms 94312 KB Output is correct
13 Correct 47 ms 94604 KB Output is correct
14 Correct 49 ms 94692 KB Output is correct
15 Correct 42 ms 94112 KB Output is correct
16 Correct 43 ms 94176 KB Output is correct
17 Correct 42 ms 94156 KB Output is correct
18 Correct 577 ms 112032 KB Output is correct
19 Correct 210 ms 98232 KB Output is correct
20 Correct 171 ms 97788 KB Output is correct
21 Correct 192 ms 97828 KB Output is correct
22 Correct 195 ms 97956 KB Output is correct
23 Correct 217 ms 98252 KB Output is correct
24 Correct 170 ms 97824 KB Output is correct
25 Correct 184 ms 98008 KB Output is correct
26 Correct 206 ms 98072 KB Output is correct
27 Correct 320 ms 109576 KB Output is correct
28 Correct 260 ms 103388 KB Output is correct
29 Correct 312 ms 108316 KB Output is correct
30 Correct 486 ms 126136 KB Output is correct
31 Correct 43 ms 94276 KB Output is correct
32 Correct 472 ms 109436 KB Output is correct

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 94156 KB Output is correct
2 Correct 45 ms 94424 KB Output is correct
3 Correct 43 ms 94356 KB Output is correct
4 Correct 43 ms 94304 KB Output is correct
5 Correct 48 ms 94452 KB Output is correct
6 Correct 43 ms 94152 KB Output is correct
7 Correct 43 ms 94224 KB Output is correct
8 Correct 43 ms 94200 KB Output is correct
9 Correct 43 ms 94228 KB Output is correct
10 Correct 42 ms 94156 KB Output is correct
11 Correct 44 ms 94284 KB Output is correct
12 Correct 44 ms 94312 KB Output is correct
13 Correct 47 ms 94604 KB Output is correct
14 Correct 49 ms 94692 KB Output is correct
15 Correct 42 ms 94112 KB Output is correct
16 Correct 43 ms 94176 KB Output is correct
17 Correct 42 ms 94156 KB Output is correct
18 Correct 577 ms 112032 KB Output is correct
19 Correct 210 ms 98232 KB Output is correct
20 Correct 171 ms 97788 KB Output is correct
21 Correct 192 ms 97828 KB Output is correct
22 Correct 195 ms 97956 KB Output is correct
23 Correct 217 ms 98252 KB Output is correct
24 Correct 170 ms 97824 KB Output is correct
25 Correct 184 ms 98008 KB Output is correct
26 Correct 206 ms 98072 KB Output is correct
27 Correct 320 ms 109576 KB Output is correct
28 Correct 260 ms 103388 KB Output is correct
29 Correct 312 ms 108316 KB Output is correct
30 Correct 486 ms 126136 KB Output is correct
31 Correct 43 ms 94276 KB Output is correct
32 Correct 472 ms 109436 KB Output is correct
33 Execution timed out 3082 ms 125516 KB Time limit exceeded
34 Halted 0 ms 0 KB -