oj.uz

Submission #221816

# Submission time Handle Problem Language Result Execution time Memory
221816 2020-04-11T08:04:05 Z patrikpavic2 Land of the Rainbow Gold (APIO17_rainbow) C++17
12 / 100
 310 ms 55908 KB 
/**
* 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.0

# Verdict Execution time Memory Grader output
1 Runtime error 23 ms 16512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 31736 KB Output is correct
2 Correct 33 ms 31736 KB Output is correct
3 Correct 226 ms 47160 KB Output is correct
4 Correct 302 ms 55908 KB Output is correct
5 Correct 310 ms 55640 KB Output is correct
6 Correct 261 ms 50148 KB Output is correct
7 Correct 289 ms 49892 KB Output is correct
8 Correct 113 ms 35320 KB Output is correct
9 Correct 300 ms 55900 KB Output is correct
10 Correct 303 ms 55620 KB Output is correct
11 Correct 269 ms 50144 KB Output is correct
12 Correct 284 ms 54344 KB Output is correct
13 Correct 274 ms 55908 KB Output is correct
14 Correct 290 ms 55808 KB Output is correct
15 Correct 242 ms 50140 KB Output is correct
16 Correct 277 ms 49788 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 31744 KB Output is correct
2 Runtime error 250 ms 48608 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 23 ms 16512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 23 ms 16512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -