Submission #221816

#	Time	Username	Problem	Language	Result	Execution time	Memory
221816		patrikpavic2	Land of the Rainbow Gold (APIO17_rainbow)	C++17	12 / 100	310 ms	55908 KiB

rainbow

/**
* user:  ppavic
* fname: Patrik
* lname: Pavić
* task:  rainbow
* score: 12.0
* date:  2019-07-10 11:35:58.592760
*/
#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);
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{
	int pref[10][N];
	void add(vector < pt > &v){
		for(pt x : v) pref[x.X][x.Y]++;
		for(int i = 0;i < 10;i++){
			int cur = 0;
			for(int j = 0;j < N;j++){
				cur += pref[i][j];
				pref[i][j] = cur;
				if(i) pref[i][j] += pref[i - 1][j];
			}
		}
	}
	int get2d(int x1,int x2,int y1,int y2){
		if(x1 > x2 || y1 > y2) return 0;
		return pref[x2][y2] - pref[x1 - 1][y2] - pref[x2][y1 - 1] + pref[x1 - 1][y1 - 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;
}

• Subtask 1: 0 / 11
• Subtask 2: 12 / 12
• Subtask 3: 0 / 24
• Subtask 4: 0 / 27
• Subtask 5: 0 / 26