oj.uz

Submission #118412

# Submission time Handle Problem Language Result Execution time Memory
118412 2019-06-19T01:08:52 Z tmwilliamlin168 Land of the Rainbow Gold (APIO17_rainbow) C++14
100 / 100
 1954 ms 210500 KB 
#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;

const int mxN=2e5, mxSTS=(6e5+9)*19+1;
int sts=1, st[mxSTS], lc[mxSTS], rc[mxSTS];

struct dat {
	set<int> ta[mxN+1];
	int rt[mxN+2];
	void a(array<int, 2> a) {
		ta[a[0]].insert(a[1]);
	}
	void bld() {
		for(int i=0; i<=mxN; ++i) {
			rt[i+1]=rt[i];
			for(int j : ta[i])
				upd(j, rt[i+1]);
		}
	}
	void upd(int l1, int &i, int l2=0, int r2=mxN) {
		st[sts]=st[i]+1;
		lc[sts]=lc[i];
		rc[sts]=rc[i];
		i=sts++;
		if(l2==r2)
			return;
		int m2=(l2+r2)/2;
		if(l1<=m2)
			upd(l1, lc[i], l2, m2);
		else
			upd(l1, rc[i], m2+1, r2);
	}
	int qry(int l1, int r1, int l2, int r2) {
		return l2>r2?0:qry(l2, r2, rt[r1+1], 0, mxN)-qry(l2, r2, rt[l1], 0, mxN);
	}
	int qry(int l1, int r1, int i, int l2, int r2) {
		if(l1<=l2&&r2<=r1)
			return st[i];
		int m2=(l2+r2)/2;
		return (l1<=m2?qry(l1, r1, lc[i], l2, m2):0)+(m2<r1?qry(l1, r1, rc[i], m2+1, r2):0);
	}
} sv, ser, sec, ss;

void init(int r, int c, int sr, int sc, int m, char *s) {
	set<array<int, 2>> cs{{--sr, --sc}};
	for(int i=0; i<m; ++i) {
		if(s[i]=='N')
			--sr;
		else if(s[i]=='S')
			++sr;
		else if(s[i]=='E')
			++sc;
		else
			--sc;
		cs.insert({sr, sc});
	}
	for(auto a : cs) {
		sv.a(a);
		sv.a({a[0], a[1]+1});
		sv.a({a[0]+1, a[1]});
		sv.a({a[0]+1, a[1]+1});
		ser.a(a);
		ser.a({a[0]+1, a[1]});
		sec.a(a);
		sec.a({a[0], a[1]+1});
		ss.a(a);
	}
	sv.bld();
	ser.bld();
	sec.bld();
	ss.bld();
}

int colour(int ar, int ac, int br, int bc) {
	--ar, --ac, --br, --bc;
	int e=2*(br-ar+bc-ac+2)+ser.qry(ar+1, br, ac, bc)+sec.qry(ar, br, ac+1, bc);
	int v=2*(br-ar+bc-ac+2)+sv.qry(ar+1, br, ac+1, bc);
	int s=ss.qry(ar, br, ac, bc);
	int c=!sv.qry(ar+1, br, ac+1, bc)||ser.qry(ar+1, br, ac, bc)-ser.qry(ar+1, br, ac+1, bc-1)||sec.qry(ar, br, ac+1, bc)-sec.qry(ar+1, br-1, ac+1, bc)?1:2;
    return e-v+c-s;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 41344 KB Output is correct
2 Correct 47 ms 42368 KB Output is correct
3 Correct 45 ms 41336 KB Output is correct
4 Correct 45 ms 41464 KB Output is correct
5 Correct 48 ms 42744 KB Output is correct
6 Correct 41 ms 41080 KB Output is correct
7 Correct 41 ms 41052 KB Output is correct
8 Correct 41 ms 41080 KB Output is correct
9 Correct 43 ms 41080 KB Output is correct
10 Correct 41 ms 41080 KB Output is correct
11 Correct 44 ms 41564 KB Output is correct
12 Correct 46 ms 42104 KB Output is correct
13 Correct 51 ms 43256 KB Output is correct
14 Correct 49 ms 43844 KB Output is correct
15 Correct 41 ms 41080 KB Output is correct
16 Correct 42 ms 41080 KB Output is correct
17 Correct 40 ms 41000 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 41080 KB Output is correct
2 Correct 40 ms 41000 KB Output is correct
3 Correct 1006 ms 142756 KB Output is correct
4 Correct 1320 ms 209272 KB Output is correct
5 Correct 1325 ms 207968 KB Output is correct
6 Correct 1033 ms 170808 KB Output is correct
7 Correct 1254 ms 168312 KB Output is correct
8 Correct 549 ms 44796 KB Output is correct
9 Correct 1291 ms 209236 KB Output is correct
10 Correct 1316 ms 207900 KB Output is correct
11 Correct 1079 ms 171000 KB Output is correct
12 Correct 652 ms 197672 KB Output is correct
13 Correct 650 ms 209220 KB Output is correct
14 Correct 657 ms 207868 KB Output is correct
15 Correct 561 ms 170872 KB Output is correct
16 Correct 1026 ms 161000 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 41080 KB Output is correct
2 Correct 516 ms 205684 KB Output is correct
3 Correct 299 ms 205560 KB Output is correct
4 Correct 313 ms 205652 KB Output is correct
5 Correct 276 ms 164552 KB Output is correct
6 Correct 113 ms 72184 KB Output is correct
7 Correct 195 ms 103232 KB Output is correct
8 Correct 483 ms 188192 KB Output is correct
9 Correct 431 ms 171760 KB Output is correct
10 Correct 207 ms 73948 KB Output is correct
11 Correct 231 ms 121976 KB Output is correct
12 Correct 523 ms 205816 KB Output is correct
13 Correct 284 ms 205688 KB Output is correct
14 Correct 315 ms 205816 KB Output is correct
15 Correct 282 ms 164600 KB Output is correct
16 Correct 102 ms 66040 KB Output is correct
17 Correct 187 ms 103360 KB Output is correct
18 Correct 377 ms 205816 KB Output is correct
19 Correct 403 ms 206900 KB Output is correct
20 Correct 381 ms 206684 KB Output is correct
21 Correct 436 ms 188176 KB Output is correct
22 Correct 368 ms 171512 KB Output is correct
23 Correct 118 ms 73848 KB Output is correct
24 Correct 225 ms 121824 KB Output is correct
25 Correct 525 ms 205816 KB Output is correct
26 Correct 291 ms 205628 KB Output is correct
27 Correct 308 ms 205788 KB Output is correct
28 Correct 278 ms 164624 KB Output is correct
29 Correct 103 ms 66040 KB Output is correct
30 Correct 186 ms 103288 KB Output is correct
31 Correct 370 ms 206056 KB Output is correct
32 Correct 380 ms 206840 KB Output is correct
33 Correct 399 ms 206968 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 41344 KB Output is correct
2 Correct 47 ms 42368 KB Output is correct
3 Correct 45 ms 41336 KB Output is correct
4 Correct 45 ms 41464 KB Output is correct
5 Correct 48 ms 42744 KB Output is correct
6 Correct 41 ms 41080 KB Output is correct
7 Correct 41 ms 41052 KB Output is correct
8 Correct 41 ms 41080 KB Output is correct
9 Correct 43 ms 41080 KB Output is correct
10 Correct 41 ms 41080 KB Output is correct
11 Correct 44 ms 41564 KB Output is correct
12 Correct 46 ms 42104 KB Output is correct
13 Correct 51 ms 43256 KB Output is correct
14 Correct 49 ms 43844 KB Output is correct
15 Correct 41 ms 41080 KB Output is correct
16 Correct 42 ms 41080 KB Output is correct
17 Correct 40 ms 41000 KB Output is correct
18 Correct 1427 ms 128016 KB Output is correct
19 Correct 353 ms 48364 KB Output is correct
20 Correct 269 ms 45184 KB Output is correct
21 Correct 289 ms 45816 KB Output is correct
22 Correct 314 ms 46592 KB Output is correct
23 Correct 358 ms 48068 KB Output is correct
24 Correct 299 ms 45688 KB Output is correct
25 Correct 319 ms 46328 KB Output is correct
26 Correct 329 ms 46968 KB Output is correct
27 Correct 643 ms 112248 KB Output is correct
28 Correct 508 ms 77344 KB Output is correct
29 Correct 595 ms 106744 KB Output is correct
30 Correct 988 ms 209388 KB Output is correct
31 Correct 45 ms 41208 KB Output is correct
32 Correct 1020 ms 113188 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 41344 KB Output is correct
2 Correct 47 ms 42368 KB Output is correct
3 Correct 45 ms 41336 KB Output is correct
4 Correct 45 ms 41464 KB Output is correct
5 Correct 48 ms 42744 KB Output is correct
6 Correct 41 ms 41080 KB Output is correct
7 Correct 41 ms 41052 KB Output is correct
8 Correct 41 ms 41080 KB Output is correct
9 Correct 43 ms 41080 KB Output is correct
10 Correct 41 ms 41080 KB Output is correct
11 Correct 44 ms 41564 KB Output is correct
12 Correct 46 ms 42104 KB Output is correct
13 Correct 51 ms 43256 KB Output is correct
14 Correct 49 ms 43844 KB Output is correct
15 Correct 41 ms 41080 KB Output is correct
16 Correct 42 ms 41080 KB Output is correct
17 Correct 40 ms 41000 KB Output is correct
18 Correct 1427 ms 128016 KB Output is correct
19 Correct 353 ms 48364 KB Output is correct
20 Correct 269 ms 45184 KB Output is correct
21 Correct 289 ms 45816 KB Output is correct
22 Correct 314 ms 46592 KB Output is correct
23 Correct 358 ms 48068 KB Output is correct
24 Correct 299 ms 45688 KB Output is correct
25 Correct 319 ms 46328 KB Output is correct
26 Correct 329 ms 46968 KB Output is correct
27 Correct 643 ms 112248 KB Output is correct
28 Correct 508 ms 77344 KB Output is correct
29 Correct 595 ms 106744 KB Output is correct
30 Correct 988 ms 209388 KB Output is correct
31 Correct 45 ms 41208 KB Output is correct
32 Correct 1020 ms 113188 KB Output is correct
33 Correct 516 ms 205684 KB Output is correct
34 Correct 299 ms 205560 KB Output is correct
35 Correct 313 ms 205652 KB Output is correct
36 Correct 276 ms 164552 KB Output is correct
37 Correct 113 ms 72184 KB Output is correct
38 Correct 195 ms 103232 KB Output is correct
39 Correct 483 ms 188192 KB Output is correct
40 Correct 431 ms 171760 KB Output is correct
41 Correct 207 ms 73948 KB Output is correct
42 Correct 231 ms 121976 KB Output is correct
43 Correct 523 ms 205816 KB Output is correct
44 Correct 284 ms 205688 KB Output is correct
45 Correct 315 ms 205816 KB Output is correct
46 Correct 282 ms 164600 KB Output is correct
47 Correct 102 ms 66040 KB Output is correct
48 Correct 187 ms 103360 KB Output is correct
49 Correct 377 ms 205816 KB Output is correct
50 Correct 403 ms 206900 KB Output is correct
51 Correct 381 ms 206684 KB Output is correct
52 Correct 436 ms 188176 KB Output is correct
53 Correct 368 ms 171512 KB Output is correct
54 Correct 118 ms 73848 KB Output is correct
55 Correct 225 ms 121824 KB Output is correct
56 Correct 525 ms 205816 KB Output is correct
57 Correct 291 ms 205628 KB Output is correct
58 Correct 308 ms 205788 KB Output is correct
59 Correct 278 ms 164624 KB Output is correct
60 Correct 103 ms 66040 KB Output is correct
61 Correct 186 ms 103288 KB Output is correct
62 Correct 370 ms 206056 KB Output is correct
63 Correct 380 ms 206840 KB Output is correct
64 Correct 399 ms 206968 KB Output is correct
65 Correct 1923 ms 191760 KB Output is correct
66 Correct 1954 ms 175188 KB Output is correct
67 Correct 748 ms 77560 KB Output is correct
68 Correct 1154 ms 125560 KB Output is correct
69 Correct 1259 ms 209336 KB Output is correct
70 Correct 970 ms 209192 KB Output is correct
71 Correct 940 ms 209688 KB Output is correct
72 Correct 882 ms 168056 KB Output is correct
73 Correct 636 ms 69752 KB Output is correct
74 Correct 653 ms 107040 KB Output is correct
75 Correct 840 ms 209464 KB Output is correct
76 Correct 1219 ms 210500 KB Output is correct
77 Correct 1046 ms 210424 KB Output is correct
78 Correct 1006 ms 142756 KB Output is correct
79 Correct 1320 ms 209272 KB Output is correct
80 Correct 1325 ms 207968 KB Output is correct
81 Correct 1033 ms 170808 KB Output is correct
82 Correct 1254 ms 168312 KB Output is correct
83 Correct 549 ms 44796 KB Output is correct
84 Correct 1291 ms 209236 KB Output is correct
85 Correct 1316 ms 207900 KB Output is correct
86 Correct 1079 ms 171000 KB Output is correct
87 Correct 652 ms 197672 KB Output is correct
88 Correct 650 ms 209220 KB Output is correct
89 Correct 657 ms 207868 KB Output is correct
90 Correct 561 ms 170872 KB Output is correct
91 Correct 1026 ms 161000 KB Output is correct