이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |