oj.uz

답안 #622327

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
622327 2022-08-04T07:18:55 Z patrikpavic2 무지개나라 (APIO17_rainbow) C++17
12 / 100
 257 ms 55692 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 = 6e7 + 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 31 ms 31692 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 31576 KB Output is correct
2 Correct 25 ms 31644 KB Output is correct
3 Correct 191 ms 45896 KB Output is correct
4 Correct 240 ms 55516 KB Output is correct
5 Correct 249 ms 55352 KB Output is correct
6 Correct 224 ms 49812 KB Output is correct
7 Correct 233 ms 49496 KB Output is correct
8 Correct 88 ms 32444 KB Output is correct
9 Correct 245 ms 55572 KB Output is correct
10 Correct 257 ms 55360 KB Output is correct
11 Correct 213 ms 49724 KB Output is correct
12 Correct 228 ms 54012 KB Output is correct
13 Correct 244 ms 55692 KB Output is correct
14 Correct 236 ms 55252 KB Output is correct
15 Correct 198 ms 49844 KB Output is correct
16 Correct 207 ms 48992 KB Output is correct

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 31616 KB Output is correct
2 Runtime error 205 ms 24016 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

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

Subtask #5
0 / 26.0

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