#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
#define bug(x) cout << #x << " " << x << endl;
#define pii pair<int, int>
const int maxn = 2e5 + 10;
const int inf = 1e9;
map<int, map<int, int>> marc;
int n, m, q;
set<pii> proibidos;
vector<pii> todos;
vector<int> linha[maxn], coluna[maxn];
struct Rectangle{
int i1, j1, i2, j2; Rectangle( int i1, int j1, int i2, int j2 ) : i1(i1), j1(j1), i2(i2), j2(j2) {}
bool contem( pii ponto ){ return i1 <= ponto.first && ponto.first <= i2 && j1 <= ponto.second && ponto.second <= j2; }
};
bool find( set<pii>& s, pii p ){ return s.find(p) != s.end(); }
void init(int R, int C, int sr, int sc, int M, char *S) {
n = R, m = C;
Rectangle grid( 1, 1, R, C );
proibidos.insert({ sr, sc });
for( int i = 0; i < M; i++ ){
char c = S[i];
if( c == 'N' ) sr--;
if( c == 'S' ) sr++;
if( c == 'W' ) sc--;
if( c == 'E' ) sc++;
proibidos.insert({ sr, sc });
linha[sr].push_back(sc);
coluna[sc].push_back(sr);
}
for( auto [i, j] : proibidos ){
for( int di = -1; di <= 1; di ++ ){
for( int dj = -1; dj <= 1; dj++ ){
pii novo( i + di, j + dj );
if( !find(proibidos, novo) && grid.contem(novo) ){
linha[novo.first].push_back(novo.second);
coluna[novo.second].push_back(novo.first);
todos.push_back(novo);
}
}
}
}
}
void dfs( int i, int j, Rectangle grid ){
marc[i][j] = q;
int pos_j = lower_bound( linha[i].begin(), linha[i].end(), j ) - linha[i].begin();
int pos_i = lower_bound( coluna[j].begin(), coluna[j].end(), i ) - coluna[j].begin();
int di[] = { -1, 0, 1, 0 };
int dj[] = { 0, 1, 0, -1 };
for( int d = 0; d < 4; d++ ){
int vi = coluna[j][pos_i + di[d]], vj = linha[i][pos_j + dj[d]];
if( marc[vi][vj] != q && grid.contem(pii(vi, vj)) && !find( proibidos, pii( vi, vj ) ) ) dfs( vi, vj, grid );
}
}
int colour(int ar, int ac, int br, int bc) {
Rectangle grid( ar, ac, br, bc );
q++;
for( int i = ar; i <= br; i++ ){
todos.push_back(pii( i, ac ));
todos.push_back(pii( i, bc ));
linha[i].push_back(ac);
linha[i].push_back(bc);
}
for( int i = ac; i <= bc; i++ ){
todos.push_back(pii( ar, i ));
todos.push_back(pii( br, i ));
coluna[i].push_back(ar);
coluna[i].push_back(br);
}
for( int i = 1; i <= n; i++ ){
linha[i].push_back(0); linha[i].push_back(m + 1);
sort( linha[i].begin(), linha[i].end() );
linha[i].erase( unique( linha[i].begin(), linha[i].end() ), linha[i].end() );
}
for( int i = 1; i <= m; i++ ){
coluna[i].push_back(0); coluna[i].push_back(n + 1);
sort( coluna[i].begin(), coluna[i].end() );
coluna[i].erase( unique( coluna[i].begin(), coluna[i].end() ), coluna[i].end() );
}
sort( todos.begin(), todos.end() );
todos.erase( unique( todos.begin(), todos.end() ), todos.end() );
int resp = 0;
for( auto [i, j] : todos ){
if( grid.contem( pii( i, j ) ) && marc[i][j] != q && !find( proibidos, pii( i, j ) ) ){ resp++; dfs( i, j, grid ); }
}
return resp;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
9808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
9808 KB |
Output is correct |
| 2 |
Correct |
3 ms |
9852 KB |
Output is correct |
| 3 |
Execution timed out |
3047 ms |
54116 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
9808 KB |
Output is correct |
| 2 |
Incorrect |
658 ms |
81100 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
9808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
9808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
