Submission #554001

#TimeUsernameProblemLanguageResultExecution timeMemory
554001hhhhauraLand of the Rainbow Gold (APIO17_rainbow)C++14
0 / 100
437 ms302376 KiB
#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 (stderr)

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; }
      |                    ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...