| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 547333 | Victor | Land of the Rainbow Gold (APIO17_rainbow) | C++17 | 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.
// #pragma GCC target ("avx,avx2,fma")
// #pragma GCC optimize ("Ofast,inline") // O1 - O2 - O3 - Os - Ofast
// #pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define per(i, a, b) for (int i = (b)-1; i >= (a); --i)
#define trav(a, x) for (auto &a : x)
#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back
#define debug(x) cout << #x << " = " << x << endl
#define umap unordered_map
#define uset unordered_set
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;
const int INF = 1'000'000'007;
#include "rainbow.h"
int dr[] = {1, -1, 0, 0};
int dc[] = {0, 0, 1, -1};
int rows, cols, AR, AC, BR, BC,min_col,max_col;
bool yes=0;
vii segments[3];
vector<vector<bool>> grid, vis;
bool valid(int row, int col) { return AR <= row && row < BR && AC <= col && col < BC; }
void dfs(int row, int col) {
vis[row][col] = 1;
if(yes) {
min_col=min(min_col,col);
max_col=max(max_col,col);
}
// cout<<"row = "<<row<<" col = "<<col<<" grid = "<<grid[row][col]<<endl;
rep(k, 0, 4) {
int nr = row + dr[k], nc = col + dc[k];
if (valid(nr, nc) && !vis[nr][nc] && !grid[nr][nc]) dfs(nr, nc);
}
}
void init(int R, int C, int sr, int sc, int M, char *S) {
rows = R;
cols = C;
--sr;
--sc;
rep(i, 0, M) {
if (S[i] == 'S') S[i] = 0;
if (S[i] == 'N') S[i] = 1;
if (S[i] == 'E') S[i] = 2;
if (S[i] == 'W') S[i] = 3;
}
if (rows <= 50 && cols <= 50 || rows == 2) {
grid.assign(R, vector<bool>(C, 0));
grid[sr][sc] = 1;
rep(i, 0, M) {
sr += dr[S[i]];
sc += dc[S[i]];
grid[sr][sc] = 1;
}
// rep(i,0,rows) {
// rep(j,0,cols) cout<<grid[i][j]<<' ';
// cout<<endl;
// }
// cout<<endl;
}
if (rows == 2) {
yes=1;
AC=0;
BC=rows;
rep(k, 0, 3) {
segments[k].emplace_back(-1,-1);
if(!k) {
AR=0;
BR=1;
}
if(k==1) {
AR=1;
BR=2;
}
if(k==2) {
AR=0;
BR=2;
}
vis.assign(rows, vector<bool>(cols, 0));
rep(i, AR, BR) {
rep(j, AC, BC) {
if (vis[i][j] || grid[i][j]) continue;
min_col=INF;
max_col=0;
dfs(i, j);
segments[k].emplace_back(min_col,max_col);
}
}
}
yes=0;
}
}
int colour(int ar, int ac, int br, int bc) {
int ans = 0;
if (rows <= 50 && cols <= 50) {
--ar;
--ac;
AR = ar;
AC = ac;
BR = br;
BC = bc;
vis.assign(rows, vector<bool>(cols, 0));
rep(i, ar, br) {
rep(j, ac, bc) {
if (vis[i][j] || grid[i][j]) continue;
++ans;
dfs(i, j);
}
}
}
else if(rows==2) {
int k=0;
if(br==2) k=2-ar;
auto it_left=upper_bound(all(segments[k]),ii(ac,INF));
if(it_left!=segments[k].begin()) {
--it_left;
if(it_left->second<ac) ++it_left;
}
auto it_right=upper_bound(all(segments[k]),ii(bc,INF));
--it_right;
int lpos=it_left-segments[k].begin();
int rpos=it_right-segments[k].begin();
ans=max(0,rpos-lpos+1);
}
return ans;
}
#include <stdio.h>
#include "rainbow.h"
static int R, C, M, Q;
static int sr, sc;
static char S[100000 + 5];
int main() {
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;
}