oj.uz

Submission #409404

# Submission time Handle Problem Language Result Execution time Memory
409404 2021-05-20T16:28:16 Z cheissmart Land of the Rainbow Gold (APIO17_rainbow) C++14
100 / 100
 1597 ms 435840 KB 
#ifndef CHEISSMART
#include "rainbow.h"
#endif
#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

string _reset = "\u001b[0m", _yellow = "\u001b[33m", _bold = "\u001b[1m";
void DBG() { cerr << "]" << _reset << endl; }
template<class H, class...T> void DBG(H h, T ...t) {
	cerr << to_string(h);
	if(sizeof ...(t)) cerr << ", ";
	DBG(t...);
}
#ifdef CHEISSMART
#define debug(...) cerr << _yellow << _bold << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define debug(...)
#endif

const int INF = 1e9 + 7, N = 2e5 + 7;
string dir = "NSWE";
int di[] = {-1, 1, 0, 0}, dj[] = {0, 0, -1, 1};
int R, C;

struct qry_2D {
	struct node {
		node *l, *r;
		int sum;
		node(int _sum = 0) {
			sum = _sum;
			l = r = nullptr;
		}
		node(node* _l, node* _r) {
			l = _l, r = _r;
			sum = (l ? l -> sum : 0) + (r ? r -> sum : 0);
		}
	};
	node* p[N];
	node* add(node* t, int pos, int tl = 0, int tr = C) {
		if(!t) t = new node();
		if(tr - tl == 1) return new node(1 + t -> sum);
		int tm = (tl + tr) / 2;
		if(pos < tm) return new node(add(t -> l, pos, tl, tm), t -> r);
		else return new node(t -> l, add(t -> r, pos, tm, tr));
	}
	int qry(node* t, int l, int r, int tl = 0, int tr = C) {
		if(!t) return 0;
		if(l <= tl && tr <= r) return t -> sum;
		int tm = (tl + tr) / 2, ans = 0;
		if(l < tm) ans += qry(t -> l, l, r, tl, tm);
		if(r > tm) ans += qry(t -> r, l, r, tm, tr);
		return ans;
	}
	vi todo[N];
	void add(int x, int y) {
		todo[x].PB(y);
	}
	int qry(int xl, int xr, int yl, int yr) { // [xl, xr] x [yl, yr]
		if(xl > xr || yl > yr) return 0;
		return qry(p[xr], yl, yr + 1) - qry((xl ? p[xl - 1] : nullptr), yl, yr + 1);
	}
	void build() {
		node* lst = nullptr;
		for(int i = 0; i < R; i++) {
			for(int y:todo[i])
				lst = add(lst, y);
			p[i] = lst;
		}
	}
} cell, node, hor, ver;

#define do_once static set<pi> vis; if(vis.count({r, c})) return; vis.insert({r, c});

void init(int R, int C, int sr, int sc, int M, char *S) {
	::R = R + 1, ::C = C + 1;
	auto mark_node = [&] (int r, int c) {
		do_once
		node.add(r, c);
	};
	auto mark_hor = [&] (int r, int c) {
		do_once
		hor.add(r, c);
	};
	auto mark_ver = [&] (int r, int c) {
		do_once
		ver.add(r, c);
	};
	auto arrive = [&] (int r, int c) {
		do_once
		cell.add(r, c);
		mark_ver(r, c), mark_hor(r, c);
		mark_ver(r, c - 1);
		mark_hor(r - 1, c);
		mark_node(r, c), mark_node(r - 1, c), mark_node(r, c - 1), mark_node(r - 1, c - 1);
	};
	arrive(sr, sc);
	for(int i = 0; i < M; i++) {
		int k = find(ALL(dir), S[i]) - dir.begin();
		sr += di[k], sc += dj[k];
		arrive(sr, sc);
	}
	cell.build(), ver.build(), hor.build(), node.build();
}

int colour(int ar, int ac, int br, int bc) {
	// F = C + E - V
	ll V = (ll) (br - ar + 2) * (bc - ac + 2);
	ll E = (br - ar + 1) * 2 + (bc - ac + 1) * 2
	       + ver.qry(ar, br, ac, bc - 1)
	       + hor.qry(ar, br - 1, ac, bc);
	ll bad_nodes = node.qry(ar, br - 1, ac, bc - 1);
	ll C = V - ((br - ar + 2) * 2 + (bc - ac + 2) * 2 - 4 - 1);
	if(bad_nodes) C -= bad_nodes - 1;
	if(node.qry(ar - 1, ar - 1, ac - 1, bc) || node.qry(br, br, ac - 1, bc) || 
	   node.qry(ar - 1, br, ac - 1, ac - 1) || node.qry(ar - 1, br, bc, bc)) {
		if(bad_nodes)
			C--;
	}
	ll F = C + E - V;
	F -= cell.qry(ar, br, ac, bc);
	return F;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19332 KB Output is correct
2 Correct 16 ms 20448 KB Output is correct
3 Correct 13 ms 19468 KB Output is correct
4 Correct 14 ms 19532 KB Output is correct
5 Correct 17 ms 20684 KB Output is correct
6 Correct 11 ms 19032 KB Output is correct
7 Correct 11 ms 19036 KB Output is correct
8 Correct 11 ms 19044 KB Output is correct
9 Correct 11 ms 19040 KB Output is correct
10 Correct 10 ms 19020 KB Output is correct
11 Correct 14 ms 19636 KB Output is correct
12 Correct 15 ms 20016 KB Output is correct
13 Correct 21 ms 21232 KB Output is correct
14 Correct 19 ms 21580 KB Output is correct
15 Correct 11 ms 19020 KB Output is correct
16 Correct 12 ms 19020 KB Output is correct
17 Correct 11 ms 19020 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19020 KB Output is correct
2 Correct 11 ms 19020 KB Output is correct
3 Correct 704 ms 263460 KB Output is correct
4 Correct 1130 ms 428776 KB Output is correct
5 Correct 1110 ms 423764 KB Output is correct
6 Correct 843 ms 326752 KB Output is correct
7 Correct 1068 ms 321600 KB Output is correct
8 Correct 96 ms 22720 KB Output is correct
9 Correct 1167 ms 428728 KB Output is correct
10 Correct 1175 ms 423580 KB Output is correct
11 Correct 933 ms 326596 KB Output is correct
12 Correct 851 ms 400844 KB Output is correct
13 Correct 884 ms 428680 KB Output is correct
14 Correct 955 ms 423600 KB Output is correct
15 Correct 768 ms 326844 KB Output is correct
16 Correct 799 ms 309836 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19020 KB Output is correct
2 Correct 896 ms 432136 KB Output is correct
3 Correct 792 ms 410588 KB Output is correct
4 Correct 893 ms 423608 KB Output is correct
5 Correct 697 ms 319780 KB Output is correct
6 Correct 209 ms 97168 KB Output is correct
7 Correct 343 ms 168548 KB Output is correct
8 Correct 723 ms 330940 KB Output is correct
9 Correct 610 ms 287804 KB Output is correct
10 Correct 140 ms 73536 KB Output is correct
11 Correct 394 ms 188648 KB Output is correct
12 Correct 845 ms 432232 KB Output is correct
13 Correct 779 ms 410696 KB Output is correct
14 Correct 836 ms 423552 KB Output is correct
15 Correct 613 ms 319804 KB Output is correct
16 Correct 142 ms 82752 KB Output is correct
17 Correct 318 ms 168772 KB Output is correct
18 Correct 757 ms 407896 KB Output is correct
19 Correct 810 ms 424432 KB Output is correct
20 Correct 835 ms 424156 KB Output is correct
21 Correct 716 ms 330928 KB Output is correct
22 Correct 606 ms 287744 KB Output is correct
23 Correct 140 ms 73540 KB Output is correct
24 Correct 376 ms 188712 KB Output is correct
25 Correct 856 ms 432256 KB Output is correct
26 Correct 759 ms 410688 KB Output is correct
27 Correct 890 ms 423776 KB Output is correct
28 Correct 590 ms 319936 KB Output is correct
29 Correct 142 ms 82632 KB Output is correct
30 Correct 314 ms 168752 KB Output is correct
31 Correct 749 ms 407988 KB Output is correct
32 Correct 794 ms 424436 KB Output is correct
33 Correct 809 ms 424300 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19332 KB Output is correct
2 Correct 16 ms 20448 KB Output is correct
3 Correct 13 ms 19468 KB Output is correct
4 Correct 14 ms 19532 KB Output is correct
5 Correct 17 ms 20684 KB Output is correct
6 Correct 11 ms 19032 KB Output is correct
7 Correct 11 ms 19036 KB Output is correct
8 Correct 11 ms 19044 KB Output is correct
9 Correct 11 ms 19040 KB Output is correct
10 Correct 10 ms 19020 KB Output is correct
11 Correct 14 ms 19636 KB Output is correct
12 Correct 15 ms 20016 KB Output is correct
13 Correct 21 ms 21232 KB Output is correct
14 Correct 19 ms 21580 KB Output is correct
15 Correct 11 ms 19020 KB Output is correct
16 Correct 12 ms 19020 KB Output is correct
17 Correct 11 ms 19020 KB Output is correct
18 Correct 1008 ms 143036 KB Output is correct
19 Correct 350 ms 28100 KB Output is correct
20 Correct 223 ms 23152 KB Output is correct
21 Correct 272 ms 24052 KB Output is correct
22 Correct 300 ms 25232 KB Output is correct
23 Correct 362 ms 27996 KB Output is correct
24 Correct 224 ms 23772 KB Output is correct
25 Correct 264 ms 24784 KB Output is correct
26 Correct 293 ms 25668 KB Output is correct
27 Correct 423 ms 120128 KB Output is correct
28 Correct 280 ms 69316 KB Output is correct
29 Correct 393 ms 111324 KB Output is correct
30 Correct 893 ms 260420 KB Output is correct
31 Correct 15 ms 19160 KB Output is correct
32 Correct 777 ms 121156 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19332 KB Output is correct
2 Correct 16 ms 20448 KB Output is correct
3 Correct 13 ms 19468 KB Output is correct
4 Correct 14 ms 19532 KB Output is correct
5 Correct 17 ms 20684 KB Output is correct
6 Correct 11 ms 19032 KB Output is correct
7 Correct 11 ms 19036 KB Output is correct
8 Correct 11 ms 19044 KB Output is correct
9 Correct 11 ms 19040 KB Output is correct
10 Correct 10 ms 19020 KB Output is correct
11 Correct 14 ms 19636 KB Output is correct
12 Correct 15 ms 20016 KB Output is correct
13 Correct 21 ms 21232 KB Output is correct
14 Correct 19 ms 21580 KB Output is correct
15 Correct 11 ms 19020 KB Output is correct
16 Correct 12 ms 19020 KB Output is correct
17 Correct 11 ms 19020 KB Output is correct
18 Correct 1008 ms 143036 KB Output is correct
19 Correct 350 ms 28100 KB Output is correct
20 Correct 223 ms 23152 KB Output is correct
21 Correct 272 ms 24052 KB Output is correct
22 Correct 300 ms 25232 KB Output is correct
23 Correct 362 ms 27996 KB Output is correct
24 Correct 224 ms 23772 KB Output is correct
25 Correct 264 ms 24784 KB Output is correct
26 Correct 293 ms 25668 KB Output is correct
27 Correct 423 ms 120128 KB Output is correct
28 Correct 280 ms 69316 KB Output is correct
29 Correct 393 ms 111324 KB Output is correct
30 Correct 893 ms 260420 KB Output is correct
31 Correct 15 ms 19160 KB Output is correct
32 Correct 777 ms 121156 KB Output is correct
33 Correct 896 ms 432136 KB Output is correct
34 Correct 792 ms 410588 KB Output is correct
35 Correct 893 ms 423608 KB Output is correct
36 Correct 697 ms 319780 KB Output is correct
37 Correct 209 ms 97168 KB Output is correct
38 Correct 343 ms 168548 KB Output is correct
39 Correct 723 ms 330940 KB Output is correct
40 Correct 610 ms 287804 KB Output is correct
41 Correct 140 ms 73536 KB Output is correct
42 Correct 394 ms 188648 KB Output is correct
43 Correct 845 ms 432232 KB Output is correct
44 Correct 779 ms 410696 KB Output is correct
45 Correct 836 ms 423552 KB Output is correct
46 Correct 613 ms 319804 KB Output is correct
47 Correct 142 ms 82752 KB Output is correct
48 Correct 318 ms 168772 KB Output is correct
49 Correct 757 ms 407896 KB Output is correct
50 Correct 810 ms 424432 KB Output is correct
51 Correct 835 ms 424156 KB Output is correct
52 Correct 716 ms 330928 KB Output is correct
53 Correct 606 ms 287744 KB Output is correct
54 Correct 140 ms 73540 KB Output is correct
55 Correct 376 ms 188712 KB Output is correct
56 Correct 856 ms 432256 KB Output is correct
57 Correct 759 ms 410688 KB Output is correct
58 Correct 890 ms 423776 KB Output is correct
59 Correct 590 ms 319936 KB Output is correct
60 Correct 142 ms 82632 KB Output is correct
61 Correct 314 ms 168752 KB Output is correct
62 Correct 749 ms 407988 KB Output is correct
63 Correct 794 ms 424436 KB Output is correct
64 Correct 809 ms 424300 KB Output is correct
65 Correct 704 ms 263460 KB Output is correct
66 Correct 1130 ms 428776 KB Output is correct
67 Correct 1110 ms 423764 KB Output is correct
68 Correct 843 ms 326752 KB Output is correct
69 Correct 1068 ms 321600 KB Output is correct
70 Correct 96 ms 22720 KB Output is correct
71 Correct 1167 ms 428728 KB Output is correct
72 Correct 1175 ms 423580 KB Output is correct
73 Correct 933 ms 326596 KB Output is correct
74 Correct 851 ms 400844 KB Output is correct
75 Correct 884 ms 428680 KB Output is correct
76 Correct 955 ms 423600 KB Output is correct
77 Correct 768 ms 326844 KB Output is correct
78 Correct 799 ms 309836 KB Output is correct
79 Correct 1575 ms 334452 KB Output is correct
80 Correct 1597 ms 291300 KB Output is correct
81 Correct 470 ms 76868 KB Output is correct
82 Correct 636 ms 192084 KB Output is correct
83 Correct 1240 ms 435840 KB Output is correct
84 Correct 951 ms 414072 KB Output is correct
85 Correct 1064 ms 427168 KB Output is correct
86 Correct 821 ms 323520 KB Output is correct
87 Correct 241 ms 86216 KB Output is correct
88 Correct 426 ms 172100 KB Output is correct
89 Correct 886 ms 411460 KB Output is correct
90 Correct 1181 ms 428120 KB Output is correct
91 Correct 1129 ms 427800 KB Output is correct