Submission #622334

#	Time	Username	Problem	Language	Result	Execution time	Memory
622334		patrikpavic2	무지개나라 (APIO17_rainbow)	C++17	100 / 100	1061 ms	393760 KiB

rainbow

/**
* user:  ppavic
* fname: Patrik
* lname: Pavić
* task:  rainbow
* score: 64.0
* date:  2019-07-10 11:24:28.756490
*/
#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) - 1;
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{
	node* root[N];
	void add(vector < pt > &v){
		sort(v.begin(), v.end());
		//printf("pocelo dodavanje\n");
		int j = 0;
		root[0] = new node();
		root[0] -> L = NULA; root[0] -> R = NULA;
		for(int i = 1;i < N;i++){
			root[i] = new node();
			root[i] -> L = root[i - 1] -> L;
			root[i] -> R = root[i - 1] -> R;
			root[i] -> cnt = root[i - 1] -> cnt;
			for(;j < v.size() && v[j].X == i;j++){
				I = v[j].Y;
				update(root[i], 0, OFF - 1);
			}		
		}
		//printf("gotovo dodavanje\n");
	}
	int get2d(int x1,int x2,int y1,int y2){
		LO = y1, HI = y2;
		return query(root[x1 - 1], root[x2], 0, OFF - 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;
}

Compilation message (stderr)

rainbow.cpp: In member function 'void per_tour::add(std::vector<std::pair<int, int> >&)':
rainbow.cpp:83:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |    for(;j < v.size() && v[j].X == i;j++){
      |         ~~^~~~~~~~~~

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