// 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);
// South-East :
if (!MP[a.first][a.second + 1] && !MP[a.first + 1][a.second] && MP[a.first + 1][a.second + 1])
V[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);
if (v == 0) // No river cell
return 1;
v += (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);
/*printf("v is : %d\n", v);
printf("e is : %d\n", e);
printf("c is : %d\n", c);
printf("sq is : %d\n", sq);*/
int f = e - v + 1 + c;
//printf("f is : %d\n", f);
return f-1 - sq;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
47 ms |
70776 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
44 ms |
70784 KB |
Output is correct |
| 2 |
Correct |
44 ms |
70780 KB |
Output is correct |
| 3 |
Correct |
426 ms |
86080 KB |
Output is correct |
| 4 |
Correct |
635 ms |
95688 KB |
Output is correct |
| 5 |
Correct |
644 ms |
94740 KB |
Output is correct |
| 6 |
Correct |
425 ms |
88424 KB |
Output is correct |
| 7 |
Correct |
481 ms |
86508 KB |
Output is correct |
| 8 |
Correct |
214 ms |
78312 KB |
Output is correct |
| 9 |
Correct |
625 ms |
92908 KB |
Output is correct |
| 10 |
Correct |
565 ms |
92524 KB |
Output is correct |
| 11 |
Correct |
474 ms |
88728 KB |
Output is correct |
| 12 |
Correct |
265 ms |
86944 KB |
Output is correct |
| 13 |
Correct |
271 ms |
88044 KB |
Output is correct |
| 14 |
Correct |
276 ms |
87976 KB |
Output is correct |
| 15 |
Correct |
288 ms |
85096 KB |
Output is correct |
| 16 |
Correct |
486 ms |
88724 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
46 ms |
70904 KB |
Output is correct |
| 2 |
Incorrect |
169 ms |
100844 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
47 ms |
70776 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
47 ms |
70776 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
