Submission #365221

#	Time	Username	Problem	Language	Result	Execution time	Memory
365221		alireza_kaviani	Land of the Rainbow Gold (APIO17_rainbow)	C++11	100 / 100	2632 ms	383592 KiB

rainbow

#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 (stderr)

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 / 11
• Subtask 2: 12 / 12
• Subtask 3: 24 / 24
• Subtask 4: 27 / 27
• Subtask 5: 26 / 26