oj.uz

Submission #622329

# Submission time Handle Problem Language Result Execution time Memory
622329 2022-08-04T07:19:54 Z patrikpavic2 Land of the Rainbow Gold (APIO17_rainbow) C++17
12 / 100
 286 ms 55756 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;
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[x] = 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.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 31744 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 31652 KB Output is correct
2 Correct 27 ms 31608 KB Output is correct
3 Correct 218 ms 45900 KB Output is correct
4 Correct 240 ms 55580 KB Output is correct
5 Correct 258 ms 55284 KB Output is correct
6 Correct 209 ms 49756 KB Output is correct
7 Correct 236 ms 49468 KB Output is correct
8 Correct 93 ms 32404 KB Output is correct
9 Correct 240 ms 55756 KB Output is correct
10 Correct 250 ms 55352 KB Output is correct
11 Correct 208 ms 49796 KB Output is correct
12 Correct 229 ms 53992 KB Output is correct
13 Correct 286 ms 55584 KB Output is correct
14 Correct 246 ms 55520 KB Output is correct
15 Correct 221 ms 49828 KB Output is correct
16 Correct 222 ms 48872 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 31620 KB Output is correct
2 Runtime error 242 ms 48384 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 31744 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 31744 KB Output isn't correct
2 Halted 0 ms 0 KB -