oj.uz

Submission #625107

# Submission time Handle Problem Language Result Execution time Memory
625107 2022-08-09T11:22:48 Z QwertyPi Land of the Rainbow Gold (APIO17_rainbow) C++14
100 / 100
 1236 ms 92172 KB 
#include "rainbow.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 2e5 + 13;

int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

int dir[256];
int bx1 = INT32_MAX, bx2 = INT32_MIN, by1 = INT32_MAX, by2 = INT32_MIN;

struct DS{
	unordered_set<ll> S;
	vector<int> bits[N];
	string name;
	DS(string _n) : name(_n){}
	void add(int x, int y){
		x++; y++;
		if(S.count(x * N + y))
			return;
		S.insert(x * N + y);
		for(int i = x; i < N; i += i & -i){
			bits[i].push_back(y);
		}
	}
	void load(){
		for(int i = 0; i < N; i++){
			sort(bits[i].begin(), bits[i].end());
		}
	}
	int qry(int x, int y){
		x++; y++;
		int ret = 0;
		for(int i = x; i; i -= i & -i){
			ret += upper_bound(bits[i].begin(), bits[i].end(), y) - bits[i].begin();
		}
		return ret;
	}
	int qry(int x1, int x2, int y1, int y2){
		return qry(x2, y2) + qry(x1 - 1, y1 - 1) - qry(x2, y1 - 1) - qry(x1 - 1, y2);
	}
} V("V"), E1("E1"), E2("E2"), SQ("SQ");

void upd(int x, int y){
	bx1 = min(bx1, x);
	bx2 = max(bx2, x);
	by1 = min(by1, y);
	by2 = max(by2, y);
	
	V.add(x, y);
	E1.add(x, y - 1);
	E1.add(x, y);
	E2.add(x - 1, y);
	E2.add(x, y);
	SQ.add(x - 1, y - 1);
	SQ.add(x - 1, y);
	SQ.add(x, y - 1);
	SQ.add(x, y);
}

void init(int R, int C, int sr, int sc, int M, char *S) {
	dir['E'] = 0;
	dir['W'] = 1;
	dir['S'] = 2;
	dir['N'] = 3;
	upd(sr, sc);
	for(int i = 0; i < M; i++){
		sr += dx[dir[S[i]]];
		sc += dy[dir[S[i]]];
		upd(sr, sc);
	}
	V.load();
	E1.load();
	E2.load();
	SQ.load();
}

int colour(int ar, int ac, int br, int bc) {
	int x1 = ar, x2 = br, y1 = ac, y2 = bc;
	int v 	= (x2 - x1 + 1) * (y2 - y1 + 1) - V.qry(x1, x2, y1, y2);
	int e1 	= (x2 - x1 + 1) * (y2 - y1) - E1.qry(x1, x2, y1, y2 - 1);
	int e2  = (x2 - x1) * (y2 - y1 + 1) - E2.qry(x1, x2 - 1, y1, y2);
	int sq  = (x2 - x1) * (y2 - y1) - SQ.qry(x1, x2 - 1, y1, y2 - 1);
    return v - e1 - e2 + sq + (x1 < bx1 && bx2 < x2 && y1 < by1 && by2 < y2);
}

Compilation message

rainbow.cpp: In function 'void init(int, int, int, int, int, char*)':
rainbow.cpp:70:19: warning: array subscript has type 'char' [-Wchar-subscripts]
   70 |   sr += dx[dir[S[i]]];
      |                ~~~^
rainbow.cpp:71:19: warning: array subscript has type 'char' [-Wchar-subscripts]
   71 |   sc += dy[dir[S[i]]];
      |                ~~~^

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 19180 KB Output is correct
2 Correct 18 ms 19704 KB Output is correct
3 Correct 14 ms 19280 KB Output is correct
4 Correct 16 ms 19284 KB Output is correct
5 Correct 18 ms 19860 KB Output is correct
6 Correct 12 ms 19028 KB Output is correct
7 Correct 11 ms 19100 KB Output is correct
8 Correct 11 ms 19056 KB Output is correct
9 Correct 12 ms 19064 KB Output is correct
10 Correct 13 ms 19072 KB Output is correct
11 Correct 15 ms 19284 KB Output is correct
12 Correct 17 ms 19412 KB Output is correct
13 Correct 19 ms 20068 KB Output is correct
14 Correct 19 ms 20412 KB Output is correct
15 Correct 12 ms 19028 KB Output is correct
16 Correct 13 ms 19104 KB Output is correct
17 Correct 12 ms 19004 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19104 KB Output is correct
2 Correct 12 ms 19004 KB Output is correct
3 Correct 371 ms 60108 KB Output is correct
4 Correct 635 ms 92088 KB Output is correct
5 Correct 599 ms 91528 KB Output is correct
6 Correct 466 ms 75556 KB Output is correct
7 Correct 493 ms 74636 KB Output is correct
8 Correct 93 ms 22748 KB Output is correct
9 Correct 567 ms 92172 KB Output is correct
10 Correct 605 ms 91532 KB Output is correct
11 Correct 490 ms 75516 KB Output is correct
12 Correct 456 ms 88052 KB Output is correct
13 Correct 482 ms 92000 KB Output is correct
14 Correct 464 ms 91528 KB Output is correct
15 Correct 379 ms 75628 KB Output is correct
16 Correct 373 ms 73528 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19028 KB Output is correct
2 Correct 252 ms 73160 KB Output is correct
3 Correct 453 ms 76784 KB Output is correct
4 Correct 346 ms 75572 KB Output is correct
5 Correct 324 ms 60416 KB Output is correct
6 Correct 90 ms 29340 KB Output is correct
7 Correct 112 ms 36852 KB Output is correct
8 Correct 854 ms 80784 KB Output is correct
9 Correct 675 ms 72508 KB Output is correct
10 Correct 107 ms 29724 KB Output is correct
11 Correct 261 ms 45796 KB Output is correct
12 Correct 258 ms 73240 KB Output is correct
13 Correct 463 ms 76704 KB Output is correct
14 Correct 366 ms 75700 KB Output is correct
15 Correct 324 ms 60548 KB Output is correct
16 Correct 78 ms 27396 KB Output is correct
17 Correct 140 ms 40516 KB Output is correct
18 Correct 384 ms 82816 KB Output is correct
19 Correct 358 ms 73636 KB Output is correct
20 Correct 376 ms 77904 KB Output is correct
21 Correct 817 ms 80780 KB Output is correct
22 Correct 674 ms 72460 KB Output is correct
23 Correct 110 ms 29792 KB Output is correct
24 Correct 266 ms 45624 KB Output is correct
25 Correct 254 ms 73256 KB Output is correct
26 Correct 470 ms 76796 KB Output is correct
27 Correct 340 ms 75600 KB Output is correct
28 Correct 324 ms 60644 KB Output is correct
29 Correct 64 ms 27464 KB Output is correct
30 Correct 150 ms 40540 KB Output is correct
31 Correct 380 ms 82788 KB Output is correct
32 Correct 341 ms 73584 KB Output is correct
33 Correct 389 ms 77976 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 19180 KB Output is correct
2 Correct 18 ms 19704 KB Output is correct
3 Correct 14 ms 19280 KB Output is correct
4 Correct 16 ms 19284 KB Output is correct
5 Correct 18 ms 19860 KB Output is correct
6 Correct 12 ms 19028 KB Output is correct
7 Correct 11 ms 19100 KB Output is correct
8 Correct 11 ms 19056 KB Output is correct
9 Correct 12 ms 19064 KB Output is correct
10 Correct 13 ms 19072 KB Output is correct
11 Correct 15 ms 19284 KB Output is correct
12 Correct 17 ms 19412 KB Output is correct
13 Correct 19 ms 20068 KB Output is correct
14 Correct 19 ms 20412 KB Output is correct
15 Correct 12 ms 19028 KB Output is correct
16 Correct 13 ms 19104 KB Output is correct
17 Correct 12 ms 19004 KB Output is correct
18 Correct 994 ms 50952 KB Output is correct
19 Correct 272 ms 21568 KB Output is correct
20 Correct 197 ms 20064 KB Output is correct
21 Correct 234 ms 20396 KB Output is correct
22 Correct 256 ms 20716 KB Output is correct
23 Correct 277 ms 21452 KB Output is correct
24 Correct 261 ms 20256 KB Output is correct
25 Correct 289 ms 20552 KB Output is correct
26 Correct 274 ms 20884 KB Output is correct
27 Correct 392 ms 43492 KB Output is correct
28 Correct 342 ms 31752 KB Output is correct
29 Correct 366 ms 41372 KB Output is correct
30 Correct 926 ms 83372 KB Output is correct
31 Correct 16 ms 19156 KB Output is correct
32 Correct 659 ms 46164 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 19180 KB Output is correct
2 Correct 18 ms 19704 KB Output is correct
3 Correct 14 ms 19280 KB Output is correct
4 Correct 16 ms 19284 KB Output is correct
5 Correct 18 ms 19860 KB Output is correct
6 Correct 12 ms 19028 KB Output is correct
7 Correct 11 ms 19100 KB Output is correct
8 Correct 11 ms 19056 KB Output is correct
9 Correct 12 ms 19064 KB Output is correct
10 Correct 13 ms 19072 KB Output is correct
11 Correct 15 ms 19284 KB Output is correct
12 Correct 17 ms 19412 KB Output is correct
13 Correct 19 ms 20068 KB Output is correct
14 Correct 19 ms 20412 KB Output is correct
15 Correct 12 ms 19028 KB Output is correct
16 Correct 13 ms 19104 KB Output is correct
17 Correct 12 ms 19004 KB Output is correct
18 Correct 994 ms 50952 KB Output is correct
19 Correct 272 ms 21568 KB Output is correct
20 Correct 197 ms 20064 KB Output is correct
21 Correct 234 ms 20396 KB Output is correct
22 Correct 256 ms 20716 KB Output is correct
23 Correct 277 ms 21452 KB Output is correct
24 Correct 261 ms 20256 KB Output is correct
25 Correct 289 ms 20552 KB Output is correct
26 Correct 274 ms 20884 KB Output is correct
27 Correct 392 ms 43492 KB Output is correct
28 Correct 342 ms 31752 KB Output is correct
29 Correct 366 ms 41372 KB Output is correct
30 Correct 926 ms 83372 KB Output is correct
31 Correct 16 ms 19156 KB Output is correct
32 Correct 659 ms 46164 KB Output is correct
33 Correct 252 ms 73160 KB Output is correct
34 Correct 453 ms 76784 KB Output is correct
35 Correct 346 ms 75572 KB Output is correct
36 Correct 324 ms 60416 KB Output is correct
37 Correct 90 ms 29340 KB Output is correct
38 Correct 112 ms 36852 KB Output is correct
39 Correct 854 ms 80784 KB Output is correct
40 Correct 675 ms 72508 KB Output is correct
41 Correct 107 ms 29724 KB Output is correct
42 Correct 261 ms 45796 KB Output is correct
43 Correct 258 ms 73240 KB Output is correct
44 Correct 463 ms 76704 KB Output is correct
45 Correct 366 ms 75700 KB Output is correct
46 Correct 324 ms 60548 KB Output is correct
47 Correct 78 ms 27396 KB Output is correct
48 Correct 140 ms 40516 KB Output is correct
49 Correct 384 ms 82816 KB Output is correct
50 Correct 358 ms 73636 KB Output is correct
51 Correct 376 ms 77904 KB Output is correct
52 Correct 817 ms 80780 KB Output is correct
53 Correct 674 ms 72460 KB Output is correct
54 Correct 110 ms 29792 KB Output is correct
55 Correct 266 ms 45624 KB Output is correct
56 Correct 254 ms 73256 KB Output is correct
57 Correct 470 ms 76796 KB Output is correct
58 Correct 340 ms 75600 KB Output is correct
59 Correct 324 ms 60644 KB Output is correct
60 Correct 64 ms 27464 KB Output is correct
61 Correct 150 ms 40540 KB Output is correct
62 Correct 380 ms 82788 KB Output is correct
63 Correct 341 ms 73584 KB Output is correct
64 Correct 389 ms 77976 KB Output is correct
65 Correct 371 ms 60108 KB Output is correct
66 Correct 635 ms 92088 KB Output is correct
67 Correct 599 ms 91528 KB Output is correct
68 Correct 466 ms 75556 KB Output is correct
69 Correct 493 ms 74636 KB Output is correct
70 Correct 93 ms 22748 KB Output is correct
71 Correct 567 ms 92172 KB Output is correct
72 Correct 605 ms 91532 KB Output is correct
73 Correct 490 ms 75516 KB Output is correct
74 Correct 456 ms 88052 KB Output is correct
75 Correct 482 ms 92000 KB Output is correct
76 Correct 464 ms 91528 KB Output is correct
77 Correct 379 ms 75628 KB Output is correct
78 Correct 373 ms 73528 KB Output is correct
79 Correct 1236 ms 83884 KB Output is correct
80 Correct 1111 ms 75908 KB Output is correct
81 Correct 383 ms 33076 KB Output is correct
82 Correct 563 ms 49264 KB Output is correct
83 Correct 592 ms 76948 KB Output is correct
84 Correct 871 ms 80304 KB Output is correct
85 Correct 729 ms 79024 KB Output is correct
86 Correct 602 ms 64128 KB Output is correct
87 Correct 231 ms 30960 KB Output is correct
88 Correct 346 ms 44068 KB Output is correct
89 Correct 589 ms 86372 KB Output is correct
90 Correct 773 ms 77100 KB Output is correct
91 Correct 641 ms 81428 KB Output is correct