| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1170914 | JelalTkm | 무지개나라 (APIO17_rainbow) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include "rainbow.h"
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
// #define int long long int
const int Nqwe = 2e5 + 10;
// const int md = 1e9 + 7;
// const int INF = 1e18;
vector<vector<int>> a(60, vector<int> (2e5 + 10));
vector<int> pref(2e5 + 10), pref1(2e5 + 10), pref2(2e5 + 10);
vector<bool> ok(2e5 + 10), ok1(2e5 + 10), ok2(2e5 + 10);
bool visited[60][Nqwe];
bool ok = 0;
bool check(int x1, int y1, int x2, int y2, int x, int y) {
return (x >= x1 && x <= x2 && y >= y1 && y <= y2);
}
int colour(int x1, int y1, int x2, int y2) {
if (!ok) {
memset(visited, 0, sizeof visited);
int ans = 0;
for (int i = x1; i <= x2; i++) {
for (int j = y1; j <= y2; j++) {
if (!visited[i][j] && !a[i][j]) {
ans++;
queue<pair<int, int>> q;
q.push({i, j});
while (!q.empty()) {
auto [u, v] = q.front();
q.pop();
if (check(x1, y1, x2, y2, u + 1, v) && !a[u + 1][v]) {
visited[u + 1][v] = 1;
q.push({u + 1, v});
}
if (check(x1, y1, x2, y2, u - 1, v) && !a[u - 1][v]) {
visited[u - 1][v] = 1;
q.push({u - 1, v});
}
if (check(x1, y1, x2, y2, u, v + 1) && !a[u][v + 1]) {
visited[u][v + 1] = 1;
q.push({u, v + 1});
}
if (check(x1, y1, x2, y2, u, v - 1) && !a[u][v - 1]) {
visited[u][v - 1] = 1;
q.push({u, v - 1});
}
}
}
}
}
return ans;
} else {
if (x1 != x2) {
return (pref[y2] - pref[y1 - 1] + ((!a[x1][y2] | !a[x2][y2])) - ok[y1]);
} else if (x1 == 1) {
return (pref1[y2] - pref1[y1 - 1] + (!a[x1][y2]) - ok1[y1]);
} else return (pref2[y2] - pref2[y2 - 1] + (!a[x1][y2]) - ok2[y1]);
}
return 0;
}
void init(int n, int m, int x, int y, int c, char *s) {
if (n == 2)
ok = 1;
a[x][y] = 1;
for (int i = 0; i < c; i++) {
if (s[i] == 'N') x--;
if (s[i] == 'S') x++;
if (s[i] == 'W') y--;
if (s[i] == 'E') y++;
a[x][y] = 1;
}
if (ok) {
for (int i = 1; i <= m; i++) {
pref[i] = pref[i - 1];
pref1[i] = pref1[i - 1];
pref2[i] = pref2[i - 1];
if (a[1][i] == 1 && a[2][i] == 1 && (i > 1 && (!a[1][i - 1] || !a[2][i - 1])))
pref[i]++, ok[i] = 1;
if (a[1][i] == 1 && (i > 1 && !a[1][i - 1]))
pref1[i]++, ok1[i] = 1;
if (a[2][i] == 1 && (i > 1 && !a[2][i - 1]))
pref2[i]++, ok2[i] = 1;
}
}
return;
}
// int32_t main(int32_t argc, char *argv[]) {
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
// int T = 1;
// // cin >> T;
// while (T--) {
// }
// return 0;
// }