| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 106469 | polyfish | Land of the Rainbow Gold (APIO17_rainbow) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
#define debug(x) cerr << #x << " = " << x << '\n';
#define BP() cerr << "OK!\n";
#define PR(A, n) {cerr << #A << " = "; for (int _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define PR0(A, n) {cerr << #A << " = "; for (int _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define FILE_NAME "data"
const int X[] = {1, 0, -1, 0};
const int Y[] = {0, 1, 0, -1};
const int INF = 1e9;
int m, n, min_x, max_x, min_y, max_y;
vector<pair<int, int> > snake;
bool visited[52][52];
void init(int R, int C, int sr, int sc, int M, char *S) {
m = R;
n = C;
max_x = max_y = -INF;
min_x = min_y = INF;
snake.resize(M+1);
snake[0] = {sr, sc};
for (int i=1; i<=M; ++i) {
snake[i] = snake[i-1];
if (S[i-1]=='N')
--snake[i].first;
else if (S[i-1]=='S')
++snake[i].first;
else if (S[i-1]=='W')
--snake[i].second;
else
++snake[i].second;
}
sort(snake.begin(), snake.end());
snake.resize(unique(snake.begin(), snake.end()) - snake.begin());
for (auto p : snake) {
min_x = min(min_x, p.first);
max_x = max(max_x, p.first);
min_y = min(min_y, p.second);
max_y = max(max_y, p.second);
}
}
void visit(int u, int v, int x1, int y1, int x2, int y2) {
visited[u][v] = true;
for (int i=0; i<4; ++i) {
int p = u + X[i], q = v + Y[i];
if (x1<=p && p<=x2 && y1<=q && q<=y2 && !visited[p][q])
visit(p, q, x1, y1, x2, y2);
}
}
int subtask1(int x1, int y1, int x2, int y2) {
memset(visited, false, sizeof(visited));
for (auto p : snake)
visited[p.first][p.second] = true;
int res = 0;
for (int i=x1; i<=x2; ++i) {
for (int j=y1; j<=y2; ++j) {
if (!visited[i][j]) {
++res;
visit(i, j, x1, y1, x2, y2);
}
}
}
return res;
}
int subtask3(int x1, int y1, int x2, int y2) {
set<pair<int, int> > v;
set<pair<pair<int, int>, pair<int, int> > > e;
int res = 0;
for (int i=x1; i<=x2+1; ++i) {
v.insert({i, y1});
v.insert({i, y2+1});
if (i<=x2) {
pair<int, int> tmp1(i, y1), tmp2(i+1, y1);
e.insert({min(tmp1, tmp2), max(tmp1, tmp2)});
pair<int, int> tmp3(i, y2+1), tmp4(i+1, y2+1);
e.insert({min(tmp3, tmp4), max(tmp3, tmp4)});
}
}
for (int i=y1; i<=y2+1; ++i) {
v.insert({x1, i});
v.insert({x2+1, i});
if (i<=y2) {
pair<int, int> tmp1(x1, i), tmp2(x1, i+1);
e.insert({min(tmp1, tmp2), max(tmp1, tmp2)});
pair<int, int> tmp3(x2+1, i), tmp4(x2+1, i+1);
e.insert({min(tmp3, tmp4), max(tmp3, tmp4)});
}
}
for (auto p : snake) {
if (x1<=p.first && p.first<=x2 && y1<=p.second && p.second<=y2) {
--res;
for (int i=0; i<4; ++i) {
v.insert(p);
pair<int, int> tmp = p;
p.first += X[i];
p.second += Y[i];
e.insert({min(p, tmp), max(p, tmp)});
}
}
}
// debug(v.size());
// debug(e.size());
res += (int)e.size() - (int)v.size() + 1;
if (x1<min_x && max_x<x2 && y1<min_y && max_y<y2)
++res;
return res;
}
int colour(int x1, int y1, int x2, int y2) {
return subtask3(x1, y1, x2, y2);
// if (m<=50 && n<=50)
// return subtask1(x1, y1, x2, y2);
// else
// return subtask3(x1, y1, x2, y2);
}
int main() {
freopen("rainbow.in", "r", stdin);
// freopen("rainbow.out", "w", stdout);
int R, C, M, Q, sr, sc;
static char S[100 + 5];
scanf("%d %d %d %d", &R, &C, &M, &Q);
scanf("%d %d", &sr, &sc);
if (M > 0) {
scanf(" %s ", S);
}
init(R, C, sr, sc, M, S);
int query;
for (query = 0; query < Q; query++) {
int ar, ac, br, bc;
scanf("%d %d %d %d", &ar, &ac, &br, &bc);
printf("%d\n", colour(ar, ac, br, bc));
}
return 0;
}