// M
#include<bits/stdc++.h>
#include "rainbow.h"
#define lc (id << 1)
#define rc (lc ^ 1)
#define md ((l + r) >> 1)
using namespace std;
const int N = 200005;
int n, m;
vector < int > V[3][N], VS[3][N * 2], R[2][N], C[2][N];
vector < pair < int , int > > A;
map < int , int > MP[N];
inline int Count(vector < int > &vec, int l, int r)
{
// [l, r)
return (int)(lower_bound(vec.begin(), vec.end(), r) - lower_bound(vec.begin(), vec.end(), l));
}
void Build(int id = 1, int l = 1, int r = n + 1)
{
if (r - l < 2)
{
for (int w = 0; w <= 2; w ++)
{
VS[w][id] = V[w][l];
sort(VS[w][id].begin(), VS[w][id].end());
}
return ;
}
Build(lc, l, md);
Build(rc, md, r);
for (int w = 0; w <= 2; w ++)
merge(VS[w][lc].begin(), VS[w][lc].end(), VS[w][rc].begin(), VS[w][rc].end(), back_inserter(VS[w][id]));
}
int Get(int w, int le, int ri, int lq, int rq, int id = 1, int l = 1, int r = n + 1)
{
if (ri <= l || r <= le)
return 0;
if (le <= l && r <= ri)
return Count(VS[w][id], lq, rq);
return Get(w, le, ri, lq, rq, lc, l, md) + Get(w, le, ri, lq, rq, rc, md, r);
}
void init(int _n, int _m, int sta, int stb, int k, char * S)
{
n = _n; m = _m;
int nwa = sta, nwb = stb;
A.push_back(make_pair(nwa, nwb));
for (int i = 0; i < k; i ++)
{
if (S[i] == 'N') nwa --;
if (S[i] == 'S') nwa ++;
if (S[i] == 'W') nwb --;
if (S[i] == 'E') nwb ++;
A.push_back(make_pair(nwa, nwb));
}
sort(A.begin(), A.end());
A.resize(unique(A.begin(), A.end()) - A.begin());
for (auto a : A)
MP[a.first][a.second] = 1;
// w = 0 is for vertices ..
for (auto a : A)
V[0][a.first].push_back(a.second);
// w = 1 is for edges ..
for (auto a : A)
{
// South :
if (MP[a.first + 1][a.second])
V[1][a.first].push_back(a.second),
C[1][a.second].push_back(a.first);
// East :
if (MP[a.first][a.second + 1])
V[1][a.first].push_back(a.second),
R[1][a.first].push_back(a.second);
// w = 2 is for squares ..
if (MP[a.first + 1][a.second] && MP[a.first][a.second + 1] && MP[a.first + 1][a.second + 1])
V[2][a.first].push_back(a.second);
}
Build();
for (auto a : A)
R[0][a.first].push_back(a.second),
C[0][a.second].push_back(a.first);
for (int i = 1; i <= n; i ++)
for (int w = 0; w <= 1; w ++)
sort(R[w][i].begin(), R[w][i].end());
for (int i = 1; i <= m; i ++)
for (int w = 0; w <= 1; w ++)
sort(C[w][i].begin(), C[w][i].end());
}
int colour(int lx, int ly, int rx, int ry)
{
// Note : if no river cell is on the border, then c = 2.
// v - e + f = 1 + c ~~~> f = e - v + 1 + c
// sq : number of 2*2 squares
// Then the answer is f-1 - sq
int v = Get(0, lx, rx + 1, ly, ry + 1) + (rx - lx + 1 + ry - ly + 1) * 2 + 4;
int e = Get(1, lx, rx, ly, ry) + (rx - lx + 1 + ry - ly + 1) * 2 + 4;
int stamp = e;
e += Count(R[0][lx], ly, ry + 1);
e += Count(R[0][rx], ly, ry + 1);
e += Count(C[0][ly], lx, rx + 1);
e += Count(C[0][ry], lx, rx + 1);
int c = 1;
if (e == stamp) // There is no border river cell
c = 2;
e += Count(R[1][rx], ly, ry);
e += Count(C[1][ry], lx, rx);
int sq = MP[lx][ly] + MP[lx][ry] + MP[rx][ly] + MP[rx][ry];
sq += Get(2, lx, rx, ly, ry);
sq += Count(R[1][lx], ly, ry);
sq += Count(R[1][rx], ly, ry);
sq += Count(C[1][ly], lx, rx);
sq += Count(C[1][ry], lx, rx);
int f = e - v + 1 + c;
return f-1 - sq;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
49 ms |
70776 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
48 ms |
70776 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
45 ms |
70904 KB |
Output is correct |
| 2 |
Incorrect |
162 ms |
100968 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
49 ms |
70776 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
49 ms |
70776 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
