oj.uz

Submission #433504

# Submission time Handle Problem Language Result Execution time Memory
433504 2021-06-19T23:29:27 Z rqi Land of the Rainbow Gold (APIO17_rainbow) C++14
11 / 100
 817 ms 110276 KB 
#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vpi;

#define mp make_pair
#define f first
#define s second
#define ins insert
#define pb push_back

#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

void ckmin(int& a, int b){
	a = min(a, b);
}

void ckmax(int& a, int b){
	a = max(a, b);
}

vector<char> dchar = vector<char>{'S', 'E', 'N', 'W'};
vi dx = vi{1, 0, -1, 0};
vi dy = vi{0, 1, 0, -1};

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

struct hashFunc{
	size_t operator()(pi a) const {
		ll res = ll(a.f)*200005+ll(a.s);
		ll BIG_RAND = 102923014203249LL;
		return __builtin_bswap64((unsigned long long)(res)*BIG_RAND);
	}
};

const int mx = 200005;

struct Off2DBIT{
	ll bt[mx];
	vi all_ys;
	int begin_index[mx];
	int num[mx];

	vpi all_updates;
	void update(int X, int Y){
		all_updates.pb(mp(X, Y));
	}

	

	void UPD(int X, int Y){
		for(int i = X; i < mx; i+=i&-i){
			int pos = lower_bound(begin(all_ys)+begin_index[i], begin(all_ys)+begin_index[i]+num[i], Y)-begin(all_ys)-begin_index[i]+1;
			for(int j = pos; j <= num[i]; j+=j&-j){
				bt[begin_index[i]-1+j]++;
			}
		}
	}

	vi to_add_ys[mx];
	int last_num[mx];

	void initBT(){
		// cout << "all_updates: " << "\n";
		// for(const auto& u: all_updates){
		// 	cout << u.f << " " << u.s << "\n";
		// }
		for(auto &u: all_updates){
			swap(u.s, u.f);
		}
		sort(all(all_updates));

		for(const auto& u: all_updates){
			for(int i = u.s; i < mx; i+=i&-i){
				if(last_num[i] != u.f){
					last_num[i] = u.f;
					to_add_ys[i].pb(u.f);
				}
			}
		}

		int cur = 0;
		for(int i = 1; i < mx; i++){
			begin_index[i] = cur;
			num[i] = sz(to_add_ys[i]);
			for(const auto& u: to_add_ys[i]){
				all_ys.pb(u);
			}
			vi v;
			swap(to_add_ys[i], v);
			cur+=num[i];
		}

		for(auto &u: all_updates){
			swap(u.s, u.f);
		}

		for(const auto& u: all_updates){
			UPD(u.f, u.s);
		}

		// cout << "all_ys: ";
		// for(auto u: all_ys){
		// 	cout << u << " ";
		// }
		// cout << "\n";
		// for(int i = 1; i < 5; i++){
		// 	cout << i << " " << begin_index[i] << " " << num[i] << "\n";
		// }
		// cout << "\n";
	}

	ll sum(int x_coor, int y_coor){
		ll res = 0;
		for(int i = x_coor; i > 0; i-=i&-i){
			int pos = upper_bound(begin(all_ys)+begin_index[i], begin(all_ys)+begin_index[i]+num[i], y_coor)-begin(all_ys)-begin_index[i];
			for(int j = pos; j > 0; j-=j&-j){
				res+=bt[begin_index[i]-1+j];
			}
		}

		// cout << "sum(" << x_coor << ", " << y_coor << "): " << res << "\n";
		return res;
	}

	ll query(int xl, int yl, int xr, int yr){
		return sum(xr, yr)-sum(xl-1, yr)-sum(xr, yl-1)+sum(xl-1, yl-1);
	}

	// ll query(int xl, int yl, int xr, int yr){
	// 	ll res = 0;
	// 	for(auto& u: all_updates){
	// 		if(xl <= u.f && u.f <= xr && yl <= u.s && u.s <= yr){
	// 			res++;
	// 		}
	// 	}
	// 	return res;
	// }
};

Off2DBIT bits[2][2];
gp_hash_table<pi, null_type, hashFunc> rects[4];

int min_sr, max_sr, min_sc, max_sc;

void init(int R, int C, int sr, int sc, int M, char *S) {
	min_sr = sr;
	min_sc = sc;
	max_sr = sr;
	max_sc = sc;
	for(int i = 0; i <= M; i++){
		for(int i = 0; i <= 1; i++){
			for(int j = 0; j <= 1; j++){
				for(int xl = sr-i; xl <= sr; xl++){
					for(int yl = sc-j; yl <= sc; yl++){
						if(1 <= xl && 1 <= yl){
							rects[2*i+j][mp(xl, yl)];
						}
					}
				}
			}
		}
		if(i < M){
			for(int d = 0; d < 4; d++){
				if(S[i] == dchar[d]){
					sr+=dx[d];
					sc+=dy[d];
					break;
				}
			}
		}

		ckmin(min_sr, sr);
		ckmin(min_sc, sc);
		ckmax(max_sr, sr);
		ckmax(max_sc, sc);
	}

	for(int i = 0; i <= 1; i++){
		for(int j = 0; j <= 1; j++){
			// cout << "i, j = " << i << ", " << j << "\n";
			for(auto u: rects[2*i+j]){
				// cout << "RECT " << i << " " << j << " " << u.f << " " << u.s << "\n";
				bits[i][j].update(u.f, u.s);
			}
		}
	}

	for(int i = 0; i <= 1; i++){
		for(int j = 0; j <= 1; j++){
			bits[i][j].initBT();
		}
	}
}

int colour(int ar, int ac, int br, int bc) {
	ll ans = 0;
	if(ar+1 <= min_sr && max_sr+1 <= br && ac+1 <= min_sc && max_sc+1 <= bc){
		ans++;
	}
	
	for(int i = 0; i <= 1; i++){
		for(int j = 0; j <= 1; j++){
			ll val = ll(br-i-ar+1)*ll(bc-j-ac+1);
			// cout << "val: " << val << "\n";
			// cout << "querying " << i << " " << j << "\n";
			val-=bits[i][j].query(ar, ac, br-i, bc-j);
			if((i+j) % 2 == 0){
				ans+=val;
			}
			else{
				ans-=val;
			}

			// cout << i << " " << j << " " << val << "\n";
		}
	}
    return (int)(ans);
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 25548 KB Output is correct
2 Correct 28 ms 25828 KB Output is correct
3 Correct 21 ms 25580 KB Output is correct
4 Correct 22 ms 25688 KB Output is correct
5 Correct 25 ms 25928 KB Output is correct
6 Correct 19 ms 25492 KB Output is correct
7 Correct 19 ms 25524 KB Output is correct
8 Correct 19 ms 25424 KB Output is correct
9 Correct 21 ms 25520 KB Output is correct
10 Correct 19 ms 25420 KB Output is correct
11 Correct 23 ms 25580 KB Output is correct
12 Correct 25 ms 25752 KB Output is correct
13 Correct 26 ms 25988 KB Output is correct
14 Correct 28 ms 26204 KB Output is correct
15 Correct 20 ms 25392 KB Output is correct
16 Correct 19 ms 25528 KB Output is correct
17 Correct 20 ms 25500 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 25528 KB Output is correct
2 Correct 20 ms 25500 KB Output is correct
3 Runtime error 619 ms 110276 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 20 ms 25392 KB Output is correct
2 Runtime error 561 ms 106740 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 21 ms 25548 KB Output is correct
2 Correct 28 ms 25828 KB Output is correct
3 Correct 21 ms 25580 KB Output is correct
4 Correct 22 ms 25688 KB Output is correct
5 Correct 25 ms 25928 KB Output is correct
6 Correct 19 ms 25492 KB Output is correct
7 Correct 19 ms 25524 KB Output is correct
8 Correct 19 ms 25424 KB Output is correct
9 Correct 21 ms 25520 KB Output is correct
10 Correct 19 ms 25420 KB Output is correct
11 Correct 23 ms 25580 KB Output is correct
12 Correct 25 ms 25752 KB Output is correct
13 Correct 26 ms 25988 KB Output is correct
14 Correct 28 ms 26204 KB Output is correct
15 Correct 20 ms 25392 KB Output is correct
16 Correct 19 ms 25528 KB Output is correct
17 Correct 20 ms 25500 KB Output is correct
18 Correct 733 ms 47684 KB Output is correct
19 Correct 282 ms 31004 KB Output is correct
20 Correct 193 ms 29256 KB Output is correct
21 Correct 213 ms 29564 KB Output is correct
22 Correct 234 ms 29700 KB Output is correct
23 Correct 260 ms 31128 KB Output is correct
24 Correct 236 ms 29360 KB Output is correct
25 Correct 258 ms 29596 KB Output is correct
26 Correct 265 ms 29936 KB Output is correct
27 Correct 410 ms 46228 KB Output is correct
28 Correct 342 ms 36000 KB Output is correct
29 Correct 424 ms 41984 KB Output is correct
30 Runtime error 817 ms 91328 KB Execution killed with signal 6
31 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 25548 KB Output is correct
2 Correct 28 ms 25828 KB Output is correct
3 Correct 21 ms 25580 KB Output is correct
4 Correct 22 ms 25688 KB Output is correct
5 Correct 25 ms 25928 KB Output is correct
6 Correct 19 ms 25492 KB Output is correct
7 Correct 19 ms 25524 KB Output is correct
8 Correct 19 ms 25424 KB Output is correct
9 Correct 21 ms 25520 KB Output is correct
10 Correct 19 ms 25420 KB Output is correct
11 Correct 23 ms 25580 KB Output is correct
12 Correct 25 ms 25752 KB Output is correct
13 Correct 26 ms 25988 KB Output is correct
14 Correct 28 ms 26204 KB Output is correct
15 Correct 20 ms 25392 KB Output is correct
16 Correct 19 ms 25528 KB Output is correct
17 Correct 20 ms 25500 KB Output is correct
18 Correct 733 ms 47684 KB Output is correct
19 Correct 282 ms 31004 KB Output is correct
20 Correct 193 ms 29256 KB Output is correct
21 Correct 213 ms 29564 KB Output is correct
22 Correct 234 ms 29700 KB Output is correct
23 Correct 260 ms 31128 KB Output is correct
24 Correct 236 ms 29360 KB Output is correct
25 Correct 258 ms 29596 KB Output is correct
26 Correct 265 ms 29936 KB Output is correct
27 Correct 410 ms 46228 KB Output is correct
28 Correct 342 ms 36000 KB Output is correct
29 Correct 424 ms 41984 KB Output is correct
30 Runtime error 817 ms 91328 KB Execution killed with signal 6
31 Halted 0 ms 0 KB -