oj.uz

답안 #570624

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
570624 2022-05-30T18:44:25 Z patrikpavic2 무지개나라 (APIO17_rainbow) C++17
12 / 100
 272 ms 55848 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 = 1e7 + 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 26 ms 31692 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 31656 KB Output is correct
2 Correct 26 ms 31656 KB Output is correct
3 Correct 186 ms 47172 KB Output is correct
4 Correct 261 ms 55784 KB Output is correct
5 Correct 264 ms 55500 KB Output is correct
6 Correct 237 ms 49976 KB Output is correct
7 Correct 272 ms 49664 KB Output is correct
8 Correct 91 ms 35344 KB Output is correct
9 Correct 255 ms 55848 KB Output is correct
10 Correct 261 ms 55584 KB Output is correct
11 Correct 227 ms 50040 KB Output is correct
12 Correct 242 ms 54324 KB Output is correct
13 Correct 244 ms 55748 KB Output is correct
14 Correct 246 ms 55512 KB Output is correct
15 Correct 208 ms 49992 KB Output is correct
16 Correct 213 ms 49672 KB Output is correct

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 31564 KB Output is correct
2 Runtime error 215 ms 48488 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 26 ms 31692 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 26 ms 31692 KB Output isn't correct
2 Halted 0 ms 0 KB -