oj.uz

Submission #622326

# Submission time Handle Problem Language Result Execution time Memory
622326 2022-08-04T07:17:58 Z patrikpavic2 Land of the Rainbow Gold (APIO17_rainbow) C++17
12 / 100
 278 ms 55796 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[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.0

# Verdict Execution time Memory Grader output
1 Incorrect 49 ms 31812 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 30 ms 31628 KB Output is correct
2 Correct 27 ms 31560 KB Output is correct
3 Correct 211 ms 47168 KB Output is correct
4 Correct 253 ms 55796 KB Output is correct
5 Correct 267 ms 55520 KB Output is correct
6 Correct 220 ms 49996 KB Output is correct
7 Correct 265 ms 49692 KB Output is correct
8 Correct 94 ms 35300 KB Output is correct
9 Correct 258 ms 55736 KB Output is correct
10 Correct 278 ms 55596 KB Output is correct
11 Correct 232 ms 49964 KB Output is correct
12 Correct 255 ms 54264 KB Output is correct
13 Correct 249 ms 55776 KB Output is correct
14 Correct 258 ms 55520 KB Output is correct
15 Correct 249 ms 50104 KB Output is correct
16 Correct 208 ms 49608 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 31572 KB Output is correct
2 Runtime error 234 ms 48476 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 49 ms 31812 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

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