#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define ii pair<int,int>
#define dbg(x) cerr << #x << ": " << x << endl;
#define raya cerr << "=================" << endl;
const int N = 2e5+5;
vector<vector<int>> grid;
int rows, cols;
map<char,ii> to = {{'N', {-1, 0}}, {'S', {1, 0}}, {'W', {0, -1}}, {'E', {0, 1}}};
int arriba[N], abajo[N], ambos[N];
set<int> nodes;
set<ii> edges;
void insertNodes(int row, int col){
int pri = col * (rows + 1) + row + 1;
nodes.insert(pri);
nodes.insert(pri+1);
nodes.insert(pri + rows+1);
nodes.insert(pri+1 + rows+1);
edges.insert({pri, pri+1});
edges.insert({pri, pri + rows+1});
edges.insert({pri+1, pri+1 + rows+1});
edges.insert({pri+rows+1, pri+1+rows+1});
}
void init(int R, int C, int sr, int sc, int M, char *s){
rows = R;
cols = C;
sr--, sc--;
if(rows == 2){
grid.assign(3, vector<int>(cols+1, 0));
} else if(rows <= 50 && cols <= 50) {
grid.assign(rows+1, vector<int>(cols+1, 0));
}
if(rows <= 50 && cols <= 50){
ii pos = {sr, sc};
grid[pos.first][pos.second] = 1;
for(int i=0; i<M; ++i){
char c = s[i];
pos.first += to[c].first;
pos.second += to[c].second;
grid[pos.first][pos.second] = 1;
}
}
if(rows == 2){
// subtask 2
arriba[0] = (grid[0][0] == 0);
abajo[0] = (grid[1][0] == 0);
for(int i=1; i<cols; ++i){
arriba[i] = (grid[0][i-1] == 1 && grid[0][i] == 0);
abajo[i] = (grid[1][i-1] == 1 && grid[1][i] == 0);
}
for(int i=1; i<cols; ++i){
arriba[i] += arriba[i-1];
abajo[i] += abajo[i-1];
}
// ambos
ambos[0] = (grid[0][0] == 0 && grid[1][0] == 0);
for(int i=1; i<cols; ++i){
if(grid[0][i-1] == 1 or grid[1][i-1] == 1){
ambos[i] = (grid[0][i] == 0 && grid[1][i] == 0);
}
}
for(int i=1; i<cols; ++i){
ambos[i] += ambos[i-1];
}
}
// subtask 3
ii pos = {sr, sc};
insertNodes(pos.first, pos.second);
for(int i=0; i<M; ++i){
char c = s[i];
pos.first += to[c].first;
pos.second += to[c].second;
insertNodes(pos.first, pos.second);
}
}
void clear(){
for(int i=0; i<rows; ++i){
for(int j=0; j<cols; ++j){
if(grid[i][j] == 2) grid[i][j] = 0;
}
}
}
vector<ii> mov = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
void dfs(int i, int j, int ar, int ac, int br, int bc){
for(auto tmp : mov){
int ni = i + tmp.first;
int nj = j + tmp.second;
if(ni >= ar && ni <= br && nj >= ac && nj <= bc && grid[ni][nj] == 0){
grid[ni][nj] = 2;
dfs(ni, nj, ar, ac, br, bc);
}
}
}
int colour(int ar, int ac, int br, int bc){
ar--, ac--;
br--, bc--;
if(rows == 2){
// subtask 2
if(ar+1 == br){
// ambos
int res = arriba[bc] + abajo[bc];
int quitar = ambos[bc];
if(ac > 0){
res -= arriba[ac-1] - (grid[0][ac-1] == 0 && grid[0][ac] == 0);
res -= abajo[ac-1] - (grid[1][ac-1] == 0 && grid[1][ac] == 0);
quitar -= ambos[ac-1] - (grid[0][ac-1] == 0 && grid[0][ac] == 0 && grid[1][ac-1] == 0 && grid[1][ac] == 0);
}
res -= quitar;
return res;
}
// arriba
if(ar == 0){
int res = arriba[bc];
if(ac > 0){
res -= arriba[ac-1] - (grid[0][ac-1] == 0 && grid[0][ac] == 0);
}
return res;
}
// abajo
assert(ar == 1);
int res = abajo[bc];
if(ac > 0){
res -= abajo[ac-1] - (grid[1][ac-1] == 0 && grid[1][ac] == 0);
}
return res;
}
if(rows <= 50 && cols <= 50){
// subtask 1
int ans = 0;
for(int i=ar; i<=br; ++i){
for(int j=ac; j<=bc; ++j){
if(grid[i][j] == 0){
ans++;
grid[i][j] = 2;
dfs(i, j, ar, ac, br, bc);
}
}
}
clear();
return ans;
}
// only one query (subtask 3)
}
int main(){
// init(4, 4, 2, 1, 3, "EES");
}
Compilation message
rainbow.cpp: In function 'int colour(int, int, int, int)':
rainbow.cpp:169:1: warning: control reaches end of non-void function [-Wreturn-type]
169 | }
| ^
/usr/bin/ld: /tmp/ccxJ7RhQ.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cci8EFdP.o:rainbow.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
