Submission #622326

#	Time	Username	Problem	Language	Result	Execution time	Memory
622326		patrikpavic2	Land of the Rainbow Gold (APIO17_rainbow)	C++17	12 / 100	278 ms	55796 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;
const int SVE = 2e7 + 500;
 
map < pt, bool > ima, ima2;
int toc = 0;
 
int cnt[SVE], L[SVE], R[SVE], TKO = 1;
 
int LO, HI, I;
 
void update(int x, int a,int b){
	cnt[x]++;
	if(a == b) return;
	if(I <= (a + b) / 2){
		int tmp = TKO++;
		L[tmp] = L[L[x]]; 
		R[tmp] = R[L[x]];
		cnt[tmp] = cnt[L[x]];		
		L[x] = tmp;
		update(L[x], a, (a + b) / 2);
	}
	else{
		int tmp = TKO++;
		L[tmp] = L[R[x]]; 
		R[tmp] = R[R[x]];
		cnt[tmp] = cnt[R[x]];		
		R[tmp] = tmp;
		update(R[x], (a + b) / 2 + 1, b);	
	}
}
 
 
int query(int x1, int x2, int a,int b){
	if(LO <= a && b <= HI) return (cnt[x2]) - (cnt[x1]);
	if(a > HI || b < LO) return 0;
	return query(L[x1], L[x2], a, (a + b) / 2) + query(R[x1], R[x2], (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) {
	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