제출 #919273

#제출 시각아이디문제언어결과실행 시간메모리
919273boris_mihov무지개나라 (APIO17_rainbow)C++17
38 / 100
71 ms20816 KiB
#include "rainbow.h" #include <algorithm> #include <iostream> #include <numeric> #include <cassert> #include <vector> typedef long long llong; const int MAXN = 1000 + 10; const int INF = 1e9; int n, m; int vertex[MAXN][MAXN]; int edgesRight[MAXN][MAXN]; int edgesDown[MAXN][MAXN]; int sides[MAXN][MAXN]; bool t[MAXN][MAXN]; int minX = INF; int maxX; int minY = INF; int maxY; void init(int R, int C, int sr, int sc, int M, char *S) { n = R; m = C; for (int i = 0 ; i < M ; ++i) { minX = std::min(minX, sr); maxX = std::max(maxX, sr); minY = std::min(minY, sc); maxY = std::max(maxY, sc); t[sr][sc] = 1; if (S[i] == 'N') { sr--; } else if (S[i] == 'E') { sc++; } else if (S[i] == 'S') { sr++; } else if (S[i] == 'W') { sc--; } else { assert(false); } } t[sr][sc] = 1; minX = std::min(minX, sr); maxX = std::max(maxX, sr); minY = std::min(minY, sc); maxY = std::max(maxY, sc); for (int i = 1 ; i <= n ; ++i) { for (int j = 1 ; j <= m ; ++j) { vertex[i][j] = !t[i][j]; if (i < n) edgesDown[i][j] = !t[i][j] && !t[i + 1][j]; if (j < m) edgesRight[i][j] = !t[i][j] && !t[i][j + 1]; if (i < n && j < m) sides[i][j] = !t[i][j] && !t[i][j + 1] && !t[i + 1][j] && !t[i + 1][j + 1]; } } for (int i = 1 ; i <= n ; ++i) { for (int j = 1 ; j <= m ; ++j) { vertex[i][j] += vertex[i - 1][j] + vertex[i][j - 1] - vertex[i - 1][j - 1]; edgesRight[i][j] += edgesRight[i - 1][j] + edgesRight[i][j - 1] - edgesRight[i - 1][j - 1]; edgesDown[i][j] += edgesDown[i - 1][j] + edgesDown[i][j - 1] - edgesDown[i - 1][j - 1]; sides[i][j] += sides[i - 1][j] + sides[i][j - 1] - sides[i - 1][j - 1]; } } } int calc(int prefix[][MAXN], int fromX, int fromY, int toX, int toY) { if (fromX > toX || fromY > toY) return 0; return prefix[toX][toY] - prefix[fromX - 1][toY] - prefix[toX][fromY - 1] + prefix[fromX - 1][fromY - 1]; } int colour(int ar, int ac, int br, int bc) { int res = 0; res += calc(vertex, ar, ac, br, bc); res += calc(sides, ar, ac, br - 1, bc - 1); if (ar < minX && ac < minY && br > maxX && bc > maxY) // another side { res++; } res -= calc(edgesRight, ar, ac, br, bc - 1); res -= calc(edgesDown, ar, ac, br - 1, bc); return res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...