oj.uz

Submission #365221

# Submission time Handle Problem Language Result Execution time Memory
365221 2021-02-11T09:27:26 Z alireza_kaviani Land of the Rainbow Gold (APIO17_rainbow) C++11
100 / 100
 2632 ms 383592 KB 
#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define X		first
#define Y		second
#define all(x)	(x).begin() , (x).end()
#define SZ(x)	int((x).size())
#define sep		' '
#define endl	'\n'
#define lc		id << 1
#define rc		lc | 1

const int MAXN = 2e5 + 10;
const int LOG = 22;
const int MOD = 1e9 + 7;
const ll INF = 2e18;

int mnx = MOD , mny = MOD , mxx = 0 , mxy = 0;
vector<pii> points , ptr[4][MAXN << 2];
vector<int> vec[4][MAXN] , seg[4][MAXN << 2];

void merge(int ind , int id){
	int ptr1 = 0 , ptr2 = 0;
	while(ptr1 < SZ(seg[ind][lc]) && ptr2 < SZ(seg[ind][rc])){
		ptr[ind][id].push_back({ptr1 , ptr2});
		if(seg[ind][lc][ptr1] < seg[ind][rc][ptr2]){
			seg[ind][id].push_back(seg[ind][lc][ptr1++]);
		}
		else{
			seg[ind][id].push_back(seg[ind][rc][ptr2++]);
		}
	}
	while(ptr1 < SZ(seg[ind][lc])){
		ptr[ind][id].push_back({ptr1 , ptr2});
		seg[ind][id].push_back(seg[ind][lc][ptr1++]);
	}
	while(ptr2 < SZ(seg[ind][rc])){
		ptr[ind][id].push_back({ptr1 , ptr2});
		seg[ind][id].push_back(seg[ind][rc][ptr2++]);
	}
	ptr[ind][id].push_back({ptr1 , ptr2});
}

void build(int ind , int id = 1 , int l = 0 , int r = MAXN){
	if(r - l == 1){
		seg[ind][id] = vec[ind][l];
		sort(all(seg[ind][id]));
		seg[ind][id].resize(unique(all(seg[ind][id])) - seg[ind][id].begin());
		return;
	}
	int mid = l + r >> 1;
	build(ind , lc , l , mid);
	build(ind , rc , mid , r);
	merge(ind , id);
}

int get(int ind , int ql , int qr , int x , int bs = -1 , int id = 1 , int l = 0 , int r = MAXN){
	if(bs == -1)	bs = lower_bound(all(seg[ind][id]) , x) - seg[ind][id].begin();
	if(qr <= l || r <= ql)	return 0;
	if(ql <= l && r <= qr)	return bs;
	int mid = l + r >> 1;
	return get(ind , ql , qr , x , ptr[ind][id][bs].X , lc , l , mid) + get(ind , ql , qr , x , ptr[ind][id][bs].Y , rc , mid , r);
}

void init(int n, int m, int sr, int sc, int M, char *S) {
	points.push_back({sr , sc});
	for(int i = 0 ; i < M ; i++){
		if(S[i] == 'N')	sr--;
		if(S[i] == 'S')	sr++;
		if(S[i] == 'W')	sc--;
		if(S[i] == 'E')	sc++;
		points.push_back({sr , sc});
	}
	for(pii i : points){
		int x = i.X , y = i.Y;
//		cout << x << sep << y << endl;
		mnx = min(mnx , x); mxx = max(mxx , x);
		mny = min(mny , y); mxy = max(mxy , y);
		vec[0][x].push_back(y);
		vec[1][x].push_back(y); vec[1][x].push_back(y - 1);
		vec[2][x].push_back(y); vec[2][x - 1].push_back(y);
		vec[3][x].push_back(y); vec[3][x].push_back(y - 1);
		vec[3][x - 1].push_back(y); vec[3][x - 1].push_back(y - 1);
	}
	build(0); build(1); build(2); build(3);
}

int colour(int ar, int ac, int br, int bc) {
	ll ans = (mnx > ar && br > mxx && mny > ac && bc > mxy) , R = br - ar + 1 , C = bc - ac + 1;
	br++; bc++;
	ans += R * C - (get(0 , ar , br , bc) - get(0 , ar , br , ac));
	ans -= R * (C - 1) - (get(1 , ar , br , bc - 1) - get(1 , ar , br , ac));
	ans -= (R - 1) * C - (get(2 , ar , br - 1 , bc) - get(2 , ar , br - 1 , ac));
	ans += (R - 1) * (C - 1) - (get(3 , ar , br - 1 , bc - 1) - get(3 , ar , br - 1 , ac));
//    cout << mnx << sep << mxx << sep << mny << sep << mxy << endl;
	return ans;
}

Compilation message

rainbow.cpp: In function 'void build(int, int, int, int)':
rainbow.cpp:56:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |  int mid = l + r >> 1;
      |            ~~^~~
rainbow.cpp: In function 'int get(int, int, int, int, int, int, int, int)':
rainbow.cpp:66:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   66 |  int mid = l + r >> 1;
      |            ~~^~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 194924 KB Output is correct
2 Correct 212 ms 196076 KB Output is correct
3 Correct 199 ms 194928 KB Output is correct
4 Correct 197 ms 194924 KB Output is correct
5 Correct 212 ms 196460 KB Output is correct
6 Correct 188 ms 194412 KB Output is correct
7 Correct 195 ms 194412 KB Output is correct
8 Correct 197 ms 194540 KB Output is correct
9 Correct 201 ms 194540 KB Output is correct
10 Correct 194 ms 194668 KB Output is correct
11 Correct 196 ms 195180 KB Output is correct
12 Correct 220 ms 195692 KB Output is correct
13 Correct 208 ms 196844 KB Output is correct
14 Correct 208 ms 197612 KB Output is correct
15 Correct 189 ms 194540 KB Output is correct
16 Correct 193 ms 194412 KB Output is correct
17 Correct 198 ms 194456 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 194412 KB Output is correct
2 Correct 198 ms 194456 KB Output is correct
3 Correct 1311 ms 278868 KB Output is correct
4 Correct 1795 ms 344132 KB Output is correct
5 Correct 1686 ms 343480 KB Output is correct
6 Correct 1205 ms 323420 KB Output is correct
7 Correct 1682 ms 313564 KB Output is correct
8 Correct 481 ms 204344 KB Output is correct
9 Correct 1731 ms 344300 KB Output is correct
10 Correct 1715 ms 343596 KB Output is correct
11 Correct 1333 ms 323416 KB Output is correct
12 Correct 787 ms 338108 KB Output is correct
13 Correct 782 ms 344156 KB Output is correct
14 Correct 813 ms 343388 KB Output is correct
15 Correct 754 ms 323580 KB Output is correct
16 Correct 1377 ms 315868 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 194540 KB Output is correct
2 Correct 419 ms 343756 KB Output is correct
3 Correct 733 ms 377436 KB Output is correct
4 Correct 610 ms 379740 KB Output is correct
5 Correct 521 ms 325288 KB Output is correct
6 Correct 280 ms 231856 KB Output is correct
7 Correct 317 ms 258016 KB Output is correct
8 Correct 426 ms 331356 KB Output is correct
9 Correct 414 ms 323292 KB Output is correct
10 Correct 268 ms 229092 KB Output is correct
11 Correct 350 ms 278368 KB Output is correct
12 Correct 416 ms 343636 KB Output is correct
13 Correct 733 ms 377564 KB Output is correct
14 Correct 615 ms 379612 KB Output is correct
15 Correct 519 ms 325212 KB Output is correct
16 Correct 289 ms 226700 KB Output is correct
17 Correct 320 ms 259168 KB Output is correct
18 Correct 452 ms 355568 KB Output is correct
19 Correct 557 ms 361820 KB Output is correct
20 Correct 574 ms 359272 KB Output is correct
21 Correct 423 ms 331484 KB Output is correct
22 Correct 416 ms 323420 KB Output is correct
23 Correct 281 ms 229092 KB Output is correct
24 Correct 358 ms 278624 KB Output is correct
25 Correct 419 ms 343776 KB Output is correct
26 Correct 728 ms 377564 KB Output is correct
27 Correct 628 ms 379740 KB Output is correct
28 Correct 516 ms 325340 KB Output is correct
29 Correct 275 ms 226752 KB Output is correct
30 Correct 327 ms 258912 KB Output is correct
31 Correct 455 ms 355548 KB Output is correct
32 Correct 558 ms 361692 KB Output is correct
33 Correct 562 ms 359132 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 194924 KB Output is correct
2 Correct 212 ms 196076 KB Output is correct
3 Correct 199 ms 194928 KB Output is correct
4 Correct 197 ms 194924 KB Output is correct
5 Correct 212 ms 196460 KB Output is correct
6 Correct 188 ms 194412 KB Output is correct
7 Correct 195 ms 194412 KB Output is correct
8 Correct 197 ms 194540 KB Output is correct
9 Correct 201 ms 194540 KB Output is correct
10 Correct 194 ms 194668 KB Output is correct
11 Correct 196 ms 195180 KB Output is correct
12 Correct 220 ms 195692 KB Output is correct
13 Correct 208 ms 196844 KB Output is correct
14 Correct 208 ms 197612 KB Output is correct
15 Correct 189 ms 194540 KB Output is correct
16 Correct 193 ms 194412 KB Output is correct
17 Correct 198 ms 194456 KB Output is correct
18 Correct 2033 ms 287936 KB Output is correct
19 Correct 694 ms 202028 KB Output is correct
20 Correct 584 ms 198636 KB Output is correct
21 Correct 646 ms 199404 KB Output is correct
22 Correct 672 ms 200300 KB Output is correct
23 Correct 690 ms 201836 KB Output is correct
24 Correct 591 ms 199404 KB Output is correct
25 Correct 681 ms 200184 KB Output is correct
26 Correct 690 ms 200940 KB Output is correct
27 Correct 1123 ms 270820 KB Output is correct
28 Correct 1045 ms 236128 KB Output is correct
29 Correct 1235 ms 261224 KB Output is correct
30 Correct 1754 ms 359348 KB Output is correct
31 Correct 206 ms 194796 KB Output is correct
32 Correct 1885 ms 273400 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 194924 KB Output is correct
2 Correct 212 ms 196076 KB Output is correct
3 Correct 199 ms 194928 KB Output is correct
4 Correct 197 ms 194924 KB Output is correct
5 Correct 212 ms 196460 KB Output is correct
6 Correct 188 ms 194412 KB Output is correct
7 Correct 195 ms 194412 KB Output is correct
8 Correct 197 ms 194540 KB Output is correct
9 Correct 201 ms 194540 KB Output is correct
10 Correct 194 ms 194668 KB Output is correct
11 Correct 196 ms 195180 KB Output is correct
12 Correct 220 ms 195692 KB Output is correct
13 Correct 208 ms 196844 KB Output is correct
14 Correct 208 ms 197612 KB Output is correct
15 Correct 189 ms 194540 KB Output is correct
16 Correct 193 ms 194412 KB Output is correct
17 Correct 198 ms 194456 KB Output is correct
18 Correct 2033 ms 287936 KB Output is correct
19 Correct 694 ms 202028 KB Output is correct
20 Correct 584 ms 198636 KB Output is correct
21 Correct 646 ms 199404 KB Output is correct
22 Correct 672 ms 200300 KB Output is correct
23 Correct 690 ms 201836 KB Output is correct
24 Correct 591 ms 199404 KB Output is correct
25 Correct 681 ms 200184 KB Output is correct
26 Correct 690 ms 200940 KB Output is correct
27 Correct 1123 ms 270820 KB Output is correct
28 Correct 1045 ms 236128 KB Output is correct
29 Correct 1235 ms 261224 KB Output is correct
30 Correct 1754 ms 359348 KB Output is correct
31 Correct 206 ms 194796 KB Output is correct
32 Correct 1885 ms 273400 KB Output is correct
33 Correct 419 ms 343756 KB Output is correct
34 Correct 733 ms 377436 KB Output is correct
35 Correct 610 ms 379740 KB Output is correct
36 Correct 521 ms 325288 KB Output is correct
37 Correct 280 ms 231856 KB Output is correct
38 Correct 317 ms 258016 KB Output is correct
39 Correct 426 ms 331356 KB Output is correct
40 Correct 414 ms 323292 KB Output is correct
41 Correct 268 ms 229092 KB Output is correct
42 Correct 350 ms 278368 KB Output is correct
43 Correct 416 ms 343636 KB Output is correct
44 Correct 733 ms 377564 KB Output is correct
45 Correct 615 ms 379612 KB Output is correct
46 Correct 519 ms 325212 KB Output is correct
47 Correct 289 ms 226700 KB Output is correct
48 Correct 320 ms 259168 KB Output is correct
49 Correct 452 ms 355568 KB Output is correct
50 Correct 557 ms 361820 KB Output is correct
51 Correct 574 ms 359272 KB Output is correct
52 Correct 423 ms 331484 KB Output is correct
53 Correct 416 ms 323420 KB Output is correct
54 Correct 281 ms 229092 KB Output is correct
55 Correct 358 ms 278624 KB Output is correct
56 Correct 419 ms 343776 KB Output is correct
57 Correct 728 ms 377564 KB Output is correct
58 Correct 628 ms 379740 KB Output is correct
59 Correct 516 ms 325340 KB Output is correct
60 Correct 275 ms 226752 KB Output is correct
61 Correct 327 ms 258912 KB Output is correct
62 Correct 455 ms 355548 KB Output is correct
63 Correct 558 ms 361692 KB Output is correct
64 Correct 562 ms 359132 KB Output is correct
65 Correct 1311 ms 278868 KB Output is correct
66 Correct 1795 ms 344132 KB Output is correct
67 Correct 1686 ms 343480 KB Output is correct
68 Correct 1205 ms 323420 KB Output is correct
69 Correct 1682 ms 313564 KB Output is correct
70 Correct 481 ms 204344 KB Output is correct
71 Correct 1731 ms 344300 KB Output is correct
72 Correct 1715 ms 343596 KB Output is correct
73 Correct 1333 ms 323416 KB Output is correct
74 Correct 787 ms 338108 KB Output is correct
75 Correct 782 ms 344156 KB Output is correct
76 Correct 813 ms 343388 KB Output is correct
77 Correct 754 ms 323580 KB Output is correct
78 Correct 1377 ms 315868 KB Output is correct
79 Correct 2605 ms 335068 KB Output is correct
80 Correct 2632 ms 327020 KB Output is correct
81 Correct 1801 ms 232772 KB Output is correct
82 Correct 1609 ms 282204 KB Output is correct
83 Correct 1679 ms 347348 KB Output is correct
84 Correct 1942 ms 381364 KB Output is correct
85 Correct 1749 ms 383592 KB Output is correct
86 Correct 1663 ms 328872 KB Output is correct
87 Correct 1247 ms 230368 KB Output is correct
88 Correct 1325 ms 262752 KB Output is correct
89 Correct 1492 ms 359444 KB Output is correct
90 Correct 1792 ms 365700 KB Output is correct
91 Correct 1523 ms 362764 KB Output is correct