oj.uz

Submission #365220

# Submission time Handle Problem Language Result Execution time Memory
365220 2021-02-11T09:22:28 Z alireza_kaviani Land of the Rainbow Gold (APIO17_rainbow) C++11
24 / 100
 733 ms 379868 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 = 0 , 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));
    return ans + (mnx > ar && br > mxx && mny > ac && bc > mxy);
}

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
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 194796 KB Output is correct
2 Correct 218 ms 196076 KB Output is correct
3 Incorrect 204 ms 195052 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 194412 KB Output is correct
2 Incorrect 205 ms 194540 KB Output isn't correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 194412 KB Output is correct
2 Correct 423 ms 343764 KB Output is correct
3 Correct 720 ms 377692 KB Output is correct
4 Correct 673 ms 379868 KB Output is correct
5 Correct 540 ms 325340 KB Output is correct
6 Correct 289 ms 231904 KB Output is correct
7 Correct 319 ms 258016 KB Output is correct
8 Correct 438 ms 331612 KB Output is correct
9 Correct 429 ms 323420 KB Output is correct
10 Correct 275 ms 229092 KB Output is correct
11 Correct 348 ms 278496 KB Output is correct
12 Correct 421 ms 343784 KB Output is correct
13 Correct 731 ms 377564 KB Output is correct
14 Correct 607 ms 379704 KB Output is correct
15 Correct 523 ms 325468 KB Output is correct
16 Correct 279 ms 227060 KB Output is correct
17 Correct 319 ms 259296 KB Output is correct
18 Correct 452 ms 355804 KB Output is correct
19 Correct 560 ms 361820 KB Output is correct
20 Correct 550 ms 359236 KB Output is correct
21 Correct 445 ms 331484 KB Output is correct
22 Correct 419 ms 323420 KB Output is correct
23 Correct 278 ms 229092 KB Output is correct
24 Correct 360 ms 278496 KB Output is correct
25 Correct 421 ms 343764 KB Output is correct
26 Correct 733 ms 377564 KB Output is correct
27 Correct 615 ms 379740 KB Output is correct
28 Correct 541 ms 325468 KB Output is correct
29 Correct 305 ms 226812 KB Output is correct
30 Correct 326 ms 259040 KB Output is correct
31 Correct 463 ms 355692 KB Output is correct
32 Correct 567 ms 361820 KB Output is correct
33 Correct 548 ms 359240 KB Output is correct

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 194796 KB Output is correct
2 Correct 218 ms 196076 KB Output is correct
3 Incorrect 204 ms 195052 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 194796 KB Output is correct
2 Correct 218 ms 196076 KB Output is correct
3 Incorrect 204 ms 195052 KB Output isn't correct
4 Halted 0 ms 0 KB -