oj.uz

Submission #622334

# Submission time Handle Problem Language Result Execution time Memory
622334 2022-08-04T07:25:38 Z patrikpavic2 Land of the Rainbow Gold (APIO17_rainbow) C++17
100 / 100
 1061 ms 393760 KB 
/**
* user:  ppavic
* fname: Patrik
* lname: Pavić
* task:  rainbow
* score: 64.0
* date:  2019-07-10 11:24:28.756490
*/
#include "rainbow.h"
#include <cstdio>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>

#define PB push_back
#define X first
#define Y second

using namespace std;

typedef pair < int, int > pt;

const int px[4] = {1, -1, 0, 0};
const int py[4] = {0, 0, 1, -1};

const int OFF = (1 << 18) - 1;
const int N = 2e5 + 500;

map < pt, bool > ima, ima2;
int toc = 0;

struct node{
	int cnt;
	node *L, *R;
};

int LO, HI, I;

node* NULA;

void update(node* x, int a,int b){
	x -> cnt++;
	if(a == b) return;
	if(I <= (a + b) / 2){
		node* tmp = new node();
		tmp -> L = x -> L -> L; 
		tmp -> R = x -> L -> R;
		tmp -> cnt = x -> L -> cnt;		
		x -> L = tmp;
		update(x -> L, a, (a + b) / 2);
	}
	else{
		node* tmp = new node();
		tmp -> L = x -> R -> L; 
		tmp -> R = x -> R -> R;
		tmp -> cnt = x -> R -> cnt;		
		x -> R = tmp;
		update(x -> R, (a + b) / 2 + 1, b);	
	}
}


int query(node* x1, node* x2, int a,int b){
	if(LO <= a && b <= HI) return (x2 -> cnt) - (x1 -> cnt);
	if(a > HI || b < LO) return 0;
	return query(x1 -> L, x2 -> L, a, (a + b) / 2) + query(x1 -> R, x2 -> R, (a + b) / 2 + 1, b);
}

struct per_tour{
	node* root[N];
	void add(vector < pt > &v){
		sort(v.begin(), v.end());
		//printf("pocelo dodavanje\n");
		int j = 0;
		root[0] = new node();
		root[0] -> L = NULA; root[0] -> R = NULA;
		for(int i = 1;i < N;i++){
			root[i] = new node();
			root[i] -> L = root[i - 1] -> L;
			root[i] -> R = root[i - 1] -> R;
			root[i] -> cnt = root[i - 1] -> cnt;
			for(;j < v.size() && v[j].X == i;j++){
				I = v[j].Y;
				update(root[i], 0, OFF - 1);
			}		
		}
		//printf("gotovo dodavanje\n");
	}
	int get2d(int x1,int x2,int y1,int y2){
		LO = y1, HI = y2;
		return query(root[x1 - 1], root[x2], 0, OFF - 1);
	}
};

per_tour deg[2], ob, ob2;

void init(int R, int C, int sr, int sc, int M, char *S) {
	NULA = new node(); NULA -> L = NULA; NULA -> R = NULA;
	int cx = sr, cy = sc;
	vector < pt > dod_deg0, dod_deg1, dod_ob, dod_ob2;
	ima[{cx, cy}] = 1;
	for(int i = 0;i < M;i++){
		if(S[i] == 'N') cx--;
		if(S[i] == 'S') cx++;
		if(S[i] == 'W') cy--;
		if(S[i] == 'E') cy++;
		ima[{cx, cy}] = 1;
	}
	for(pair < pt, bool > A : ima){
		pt x = A.X; //printf("POLJE %d %d\n", x.X, x.Y);
		dod_ob.PB({x.X, x.Y});
		ima2[{x.X, x.Y}] = 1;
		ima2[{x.X + 1, x.Y}] = 1;
		ima2[{x.X, x.Y + 1}] = 1;
		ima2[{x.X + 1, x.Y + 1}] = 1;
	}
	toc = (int)ima2.size();
	for(pair < pt, bool > A : ima2){
		pt x = A.X; //printf("TOCKA %d %d\n", x.X, x.Y);
		dod_ob2.PB({x.X, x.Y});
		if(ima2.count({x.X + 1, x.Y}) && (ima.count({x.X, x.Y}) || ima.count({x.X, x.Y - 1})))
			dod_deg0.PB({x.X, x.Y});
		if(ima2.count({x.X, x.Y + 1}) && (ima.count({x.X - 1, x.Y}) || ima.count({x.X, x.Y})))
			dod_deg1.PB({x.X, x.Y});
	}
	deg[0].add(dod_deg0);
	deg[1].add(dod_deg1);
	ob.add(dod_ob);
	ob2.add(dod_ob2);
}

int colour(int x1, int y1, int x2, int y2) {
	x2++, y2++;
	int E = 0;
	E += deg[0].get2d(x1    , x2 - 1, y1 + 1, y2 - 1);	
	E += deg[1].get2d(x1 + 1, x2 - 1, y1    , y2 - 1);	
	E += 2 * (x2 - x1 + y2 - y1);
	int kol = ob2.get2d(x1 + 1, x2 - 1, y1 + 1, y2 - 1); 
	int V = kol + 2 * (x2 - x1 + y2 - y1);
	//printf("V = %d E = %d\n", V, E);
	int F = E - V + 2;
	if(kol == toc) F++;
	F--; F -= ob.get2d(x1, x2 - 1, y1, y2 - 1);	
	return F;
}

Compilation message

rainbow.cpp: In member function 'void per_tour::add(std::vector<std::pair<int, int> >&)':
rainbow.cpp:83:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |    for(;j < v.size() && v[j].X == i;j++){
      |         ~~^~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 32204 KB Output is correct
2 Correct 34 ms 34596 KB Output is correct
3 Correct 31 ms 32264 KB Output is correct
4 Correct 32 ms 32508 KB Output is correct
5 Correct 36 ms 35144 KB Output is correct
6 Correct 30 ms 31704 KB Output is correct
7 Correct 31 ms 31600 KB Output is correct
8 Correct 28 ms 31652 KB Output is correct
9 Correct 31 ms 31692 KB Output is correct
10 Correct 29 ms 31636 KB Output is correct
11 Correct 33 ms 32724 KB Output is correct
12 Correct 35 ms 33868 KB Output is correct
13 Correct 38 ms 36328 KB Output is correct
14 Correct 46 ms 37376 KB Output is correct
15 Correct 29 ms 31656 KB Output is correct
16 Correct 31 ms 31652 KB Output is correct
17 Correct 29 ms 31696 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 31652 KB Output is correct
2 Correct 29 ms 31696 KB Output is correct
3 Correct 604 ms 247348 KB Output is correct
4 Correct 902 ms 393508 KB Output is correct
5 Correct 879 ms 390464 KB Output is correct
6 Correct 719 ms 307748 KB Output is correct
7 Correct 811 ms 303012 KB Output is correct
8 Correct 195 ms 32440 KB Output is correct
9 Correct 878 ms 393512 KB Output is correct
10 Correct 939 ms 390504 KB Output is correct
11 Correct 740 ms 307712 KB Output is correct
12 Correct 695 ms 368052 KB Output is correct
13 Correct 733 ms 393328 KB Output is correct
14 Correct 788 ms 390460 KB Output is correct
15 Correct 649 ms 308208 KB Output is correct
16 Correct 714 ms 287476 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 31656 KB Output is correct
2 Correct 642 ms 393344 KB Output is correct
3 Correct 597 ms 393568 KB Output is correct
4 Correct 587 ms 393552 KB Output is correct
5 Correct 481 ms 302984 KB Output is correct
6 Correct 136 ms 99576 KB Output is correct
7 Correct 237 ms 166768 KB Output is correct
8 Correct 537 ms 354596 KB Output is correct
9 Correct 490 ms 318180 KB Output is correct
10 Correct 137 ms 103264 KB Output is correct
11 Correct 292 ms 209140 KB Output is correct
12 Correct 661 ms 393572 KB Output is correct
13 Correct 582 ms 393472 KB Output is correct
14 Correct 619 ms 393628 KB Output is correct
15 Correct 467 ms 303076 KB Output is correct
16 Correct 116 ms 85928 KB Output is correct
17 Correct 225 ms 166884 KB Output is correct
18 Correct 547 ms 393412 KB Output is correct
19 Correct 618 ms 393444 KB Output is correct
20 Correct 625 ms 393228 KB Output is correct
21 Correct 537 ms 354676 KB Output is correct
22 Correct 503 ms 318092 KB Output is correct
23 Correct 139 ms 103352 KB Output is correct
24 Correct 291 ms 209064 KB Output is correct
25 Correct 651 ms 393412 KB Output is correct
26 Correct 600 ms 393520 KB Output is correct
27 Correct 590 ms 393452 KB Output is correct
28 Correct 465 ms 303040 KB Output is correct
29 Correct 139 ms 85928 KB Output is correct
30 Correct 233 ms 167040 KB Output is correct
31 Correct 579 ms 393440 KB Output is correct
32 Correct 627 ms 393420 KB Output is correct
33 Correct 602 ms 393296 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 32204 KB Output is correct
2 Correct 34 ms 34596 KB Output is correct
3 Correct 31 ms 32264 KB Output is correct
4 Correct 32 ms 32508 KB Output is correct
5 Correct 36 ms 35144 KB Output is correct
6 Correct 30 ms 31704 KB Output is correct
7 Correct 31 ms 31600 KB Output is correct
8 Correct 28 ms 31652 KB Output is correct
9 Correct 31 ms 31692 KB Output is correct
10 Correct 29 ms 31636 KB Output is correct
11 Correct 33 ms 32724 KB Output is correct
12 Correct 35 ms 33868 KB Output is correct
13 Correct 38 ms 36328 KB Output is correct
14 Correct 46 ms 37376 KB Output is correct
15 Correct 29 ms 31656 KB Output is correct
16 Correct 31 ms 31652 KB Output is correct
17 Correct 29 ms 31696 KB Output is correct
18 Correct 775 ms 215608 KB Output is correct
19 Correct 191 ms 43356 KB Output is correct
20 Correct 168 ms 36620 KB Output is correct
21 Correct 186 ms 37840 KB Output is correct
22 Correct 171 ms 39540 KB Output is correct
23 Correct 191 ms 42956 KB Output is correct
24 Correct 164 ms 37568 KB Output is correct
25 Correct 167 ms 39084 KB Output is correct
26 Correct 198 ms 40352 KB Output is correct
27 Correct 449 ms 180808 KB Output is correct
28 Correct 309 ms 105400 KB Output is correct
29 Correct 418 ms 168080 KB Output is correct
30 Correct 835 ms 393760 KB Output is correct
31 Correct 32 ms 31912 KB Output is correct
32 Correct 646 ms 182084 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 32204 KB Output is correct
2 Correct 34 ms 34596 KB Output is correct
3 Correct 31 ms 32264 KB Output is correct
4 Correct 32 ms 32508 KB Output is correct
5 Correct 36 ms 35144 KB Output is correct
6 Correct 30 ms 31704 KB Output is correct
7 Correct 31 ms 31600 KB Output is correct
8 Correct 28 ms 31652 KB Output is correct
9 Correct 31 ms 31692 KB Output is correct
10 Correct 29 ms 31636 KB Output is correct
11 Correct 33 ms 32724 KB Output is correct
12 Correct 35 ms 33868 KB Output is correct
13 Correct 38 ms 36328 KB Output is correct
14 Correct 46 ms 37376 KB Output is correct
15 Correct 29 ms 31656 KB Output is correct
16 Correct 31 ms 31652 KB Output is correct
17 Correct 29 ms 31696 KB Output is correct
18 Correct 775 ms 215608 KB Output is correct
19 Correct 191 ms 43356 KB Output is correct
20 Correct 168 ms 36620 KB Output is correct
21 Correct 186 ms 37840 KB Output is correct
22 Correct 171 ms 39540 KB Output is correct
23 Correct 191 ms 42956 KB Output is correct
24 Correct 164 ms 37568 KB Output is correct
25 Correct 167 ms 39084 KB Output is correct
26 Correct 198 ms 40352 KB Output is correct
27 Correct 449 ms 180808 KB Output is correct
28 Correct 309 ms 105400 KB Output is correct
29 Correct 418 ms 168080 KB Output is correct
30 Correct 835 ms 393760 KB Output is correct
31 Correct 32 ms 31912 KB Output is correct
32 Correct 646 ms 182084 KB Output is correct
33 Correct 642 ms 393344 KB Output is correct
34 Correct 597 ms 393568 KB Output is correct
35 Correct 587 ms 393552 KB Output is correct
36 Correct 481 ms 302984 KB Output is correct
37 Correct 136 ms 99576 KB Output is correct
38 Correct 237 ms 166768 KB Output is correct
39 Correct 537 ms 354596 KB Output is correct
40 Correct 490 ms 318180 KB Output is correct
41 Correct 137 ms 103264 KB Output is correct
42 Correct 292 ms 209140 KB Output is correct
43 Correct 661 ms 393572 KB Output is correct
44 Correct 582 ms 393472 KB Output is correct
45 Correct 619 ms 393628 KB Output is correct
46 Correct 467 ms 303076 KB Output is correct
47 Correct 116 ms 85928 KB Output is correct
48 Correct 225 ms 166884 KB Output is correct
49 Correct 547 ms 393412 KB Output is correct
50 Correct 618 ms 393444 KB Output is correct
51 Correct 625 ms 393228 KB Output is correct
52 Correct 537 ms 354676 KB Output is correct
53 Correct 503 ms 318092 KB Output is correct
54 Correct 139 ms 103352 KB Output is correct
55 Correct 291 ms 209064 KB Output is correct
56 Correct 651 ms 393412 KB Output is correct
57 Correct 600 ms 393520 KB Output is correct
58 Correct 590 ms 393452 KB Output is correct
59 Correct 465 ms 303040 KB Output is correct
60 Correct 139 ms 85928 KB Output is correct
61 Correct 233 ms 167040 KB Output is correct
62 Correct 579 ms 393440 KB Output is correct
63 Correct 627 ms 393420 KB Output is correct
64 Correct 602 ms 393296 KB Output is correct
65 Correct 604 ms 247348 KB Output is correct
66 Correct 902 ms 393508 KB Output is correct
67 Correct 879 ms 390464 KB Output is correct
68 Correct 719 ms 307748 KB Output is correct
69 Correct 811 ms 303012 KB Output is correct
70 Correct 195 ms 32440 KB Output is correct
71 Correct 878 ms 393512 KB Output is correct
72 Correct 939 ms 390504 KB Output is correct
73 Correct 740 ms 307712 KB Output is correct
74 Correct 695 ms 368052 KB Output is correct
75 Correct 733 ms 393328 KB Output is correct
76 Correct 788 ms 390460 KB Output is correct
77 Correct 649 ms 308208 KB Output is correct
78 Correct 714 ms 287476 KB Output is correct
79 Correct 1061 ms 354888 KB Output is correct
80 Correct 975 ms 318236 KB Output is correct
81 Correct 408 ms 106008 KB Output is correct
82 Correct 581 ms 210204 KB Output is correct
83 Correct 1020 ms 393620 KB Output is correct
84 Correct 927 ms 393616 KB Output is correct
85 Correct 909 ms 393712 KB Output is correct
86 Correct 742 ms 303236 KB Output is correct
87 Correct 365 ms 88852 KB Output is correct
88 Correct 475 ms 168592 KB Output is correct
89 Correct 796 ms 393660 KB Output is correct
90 Correct 953 ms 393608 KB Output is correct
91 Correct 897 ms 393376 KB Output is correct