| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 316701 | phathnv | 무지개나라 (APIO17_rainbow) | C++11 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define mp make_pair
#define X first
#define Y second
#define taskname "Rainbow"
using namespace std;
typedef long long ll;
typedef pair <int, int> ii;
const int N = 2e5 + 1;
struct segmentTree{
vector <int> d[N * 4];
void add(int id, int l, int r, int x, int y){
if (x < l || r < x)
return;
d[id].push_back(y);
if (l == r)
return;
int mid = (l + r) >> 1;
add(id << 1, l, mid, x, y);
add(id << 1 | 1, mid + 1, r, x, y);
}
void normalize(int id, int l, int r){
if (d[id].empty())
return;
sort(d[id].begin(), d[id].end());
if (l == r)
return;
int mid = (l + r) >> 1;
normalize(id << 1, l, mid);
normalize(id << 1 | 1, mid + 1, r);
}
int get(int id, int l, int r, int x1, int y1, int x2, int y2){
if (x2 < l || r < x1 || x1 > x2 || y1 > y2)
return 0;
if (d[id].empty())
return 0;
if (x1 <= l && r <= x2){
return upper_bound(d[id].begin(), d[id].end(), y2) -
lower_bound(d[id].begin(), d[id].end(), y1);
}
int mid = (l + r) >> 1;
return get(id << 1, l, mid, x1, y1, x2, y2) +
get(id << 1 | 1, mid + 1, r, x1, y1, x2, y2);
}
} cntV, cntErow, cntEcol, cntEcrs, cntF;
int r, c;
string s;
set <ii> river;
map<int, bool> isRiver[N];
void init(int R, int C, int sr, int sc, int M, char *S) {
r = R;
c = C;
isRiver[sr][sc] = 1;
river.insert(mp(sr, sc));
for(int i = 0; i < M; i++){
char ch = S[i];
if (ch == 'N')
sr--;
if (ch == 'S')
sr++;
if (ch == 'W')
sc--;
if (ch == 'E')
sc++;
isRiver[sr][sc] = 1;
river.insert(mp(sr, sc));
}
for(ii p : river){
int x = p.X;
int y = p.Y;
cntV.add(1, 1, r, x, y);
if (isRiver[x + 1][y])
cntErow.add(1, 1, r, x, y);
if (isRiver[x][y + 1])
cntEcol.add(1, 1, r, x, y);
if (isRiver[x + 1][y + 1] && !isRiver[x][y + 1] && !isRiver[x + 1][y])
cntEcrs.add(1, 1, r, x, y);
if (isRiver[x + 1][y - 1] && !isRiver[x][y - 1] && !isRiver[x + 1][y])
cntEcrs.add(1, 1, r, x, y - 1);
if (isRiver[x + 1][y] && isRiver[x][y + 1] && isRiver[x + 1][y + 1])
cntF.add(1, 1, r, x, y);
}
cntV.normalize(1, 1, r);
cntErow.normalize(1, 1, r);
cntEcol.normalize(1, 1, r);
cntEcrs.normalize(1, 1, r);
cntF.normalize(1, 1, r);
}
int colours(int ar, int ac, int br, int bc){
if (cntV.get(1, 1, r, ar, ac, br, bc) == 0)
return 1;
if (cntV.get(1, 1, r, ar, ac, br, bc) == (ll) (br - ar + 1) * (bc - ac + 1))
return 0;
int v = 2 * (br - ar + bc - ac + 4) + cntV.get(1, 1, r, ar, ac, br, bc);
int e = 2 * (br - ar + bc - ac + 4) +
cntErow.get(1, 1, r, ar, ac, br - 1, bc) +
cntEcol.get(1, 1, r, ar, ac, br, bc - 1) +
cntEcrs.get(1, 1, r, ar, ac, br - 1, bc - 1);
int f = cntF.get(1, 1, r, ar, ac, br - 1, bc - 1) + 1;
int c = 1;
if (cntV.get(1, 1, r, ar, ac, br, bc) - cntV.get(1, 1, r, ar + 1, ac + 1, br - 1, bc - 1) == 0
&& cntV.get(1, 1, r, ar + 1, ac + 1, br - 1, bc - 1) > 0)
c++;
if (ar == br && ac == bc){
if (isRiver[ar][ac]){
e += 4;
f += 4;
}
} else if (ar == br){
if (isRiver[ar][ac]){
e += 3;
f += 2;
}
if (isRiver[ar][bc]){
e += 3;
f += 2;
}
e += cntV.get(1, 1, r, ar, ac + 1, br, bc - 1) * 2;
f += 2 * cntEcol.get(1, 1, r, ar, ac, br, bc - 1);
} else if (ac == bc){
if (isRiver[ar][ac]){
e += 3;
f += 2;
}
if (isRiver[br][ac]){
e += 3;
f += 2;
}
e += cntV.get(1, 1, r, ar + 1, ac, br - 1, bc) * 2;
f += 2 * cntErow.get(1, 1, r, ar, ac, br - 1, bc);
} else {
if (isRiver[ar][ac]){
e += 2;
f += 1;
}
if (isRiver[ar][bc]){
e += 2;
f += 1;
}
if (isRiver[br][ac]){
e += 2;
f += 1;
}
if (isRiver[br][bc]){
e += 2;
f += 1;
}
e += cntV.get(1, 1, r, ar, ac + 1, ar, bc - 1) + cntV.get(1, 1, r, br, ac + 1, br, bc - 1) +
cntV.get(1, 1, r, ar + 1, ac, br - 1, ac) + cntV.get(1, 1, r, ar + 1, bc, br - 1, bc);
f += cntEcol.get(1, 1, r, ar, ac, ar, bc - 1) + cntEcol.get(1, 1, r, br, ac, br, bc - 1) +
cntErow.get(1, 1, r, ar, ac, br - 1, ac) + cntErow.get(1, 1, r, ar, bc, br - 1, bc);
}
return e + c - v + 1 - f;
}