#include "rainbow.h"
#include<bits/stdc++.h>
using namespace std;
const int inf = 1e9;
const int maxn = 2e5 + 10;
set < pair < int, int > > nodes, ver_edges, hor_edges, river;
int min_x = inf, max_x = -inf, min_y = inf, max_y = -inf;
struct fenwick_2d
{
map < int, int > data[maxn];
vector < pair < int, int > > vec[maxn];
void build()
{
for (int i = 0; i < maxn; i ++)
{
vec[i].push_back({0, 0});
for (pair < int, int > cur : data[i])
{
//if (i == 2)
{
//cout << cur.first << " ------- " << cur.second << " " << vec[i].back().second << endl;
}
int new_val = vec[i].back().second + cur.second;
vec[i].push_back({cur.first, new_val});
}
}
/**for (int i = 0; i < 10; i ++)
{
cout << "step " << i << endl;
for (int cur : vec[i])
cout << cur << " ";
cout << endl;
}*/
}
void add(int pos, int val)
{
for (int i = pos; i < maxn; i += (i & -i))
{
data[i][val] ++;
}
}
int bin_search(int idx, int val)
{
int lf = 0, rf = (int)(vec[idx].size()) - 1;
while(lf <= rf)
{
int mf = (lf + rf) / 2;
if (vec[idx][mf].first <= val)
lf = mf + 1;
else
rf = mf - 1;
}
return lf;
}
int query(int pos, int lb, int rb)
{
///cout << "QUERY " << pos << " " << lb << " " << rb << endl;
int ans = 0;
for (int i = pos; i > 0; i -= (i & -i))
{
int left = bin_search(i, lb - 1), right = bin_search(i, rb);
//cout << "left right " << left << " " << right << " " << vec[i][left].second << " :: " << vec[i][right].second << endl;
ans = ans + (vec[i][right - 1 ].second - vec[i][left - 1].second);
}
//cout << "Ans " << ans << endl;
return ans;
}
int range_query(int from, int to, int lb, int rb)
{
return query(to, lb, rb) - query(from - 1, lb, rb);
}
};
fenwick_2d fen_river;
fenwick_2d fen_nodes;
void add_node(int x, int y)
{
nodes.insert({x, y});
}
void add_hor_edge(int x, int y)
{
hor_edges.insert({x, y});
}
void add_ver_edge(int x, int y)
{
ver_edges.insert({x, y});
}
void add_river(int x, int y)
{
add_node(x, y);
add_node(x, y + 1);
add_node(x + 1, y);
add_node(x + 1, y + 1);
add_hor_edge(x, y);
add_hor_edge(x + 1, y);
add_ver_edge(x, y);
add_ver_edge(x, y + 1);
min_x = min(min_x, x);
max_x = max(max_x, x);
min_y = min(min_y, y);
max_y = max(max_y, y);
river.insert({x, y});
}
void init(int R, int C, int sr, int sc, int M, char *S)
{
add_river(sr, sc);
for (int i = 0; i < M; i ++)
{
if (S[i] == 'N')
sr --;
else
if (S[i] == 'S')
sr ++;
else
if (S[i] == 'W')
sc --;
else
if (S[i] == 'E')
sc ++;
else assert(false);
add_river(sr, sc);
}
for (pair < int, int > cur : river)
{
fen_river.add(cur.first, cur.second);
}
for (pair < int, int > cur : nodes)
{
fen_nodes.add(cur.first, cur.second);
}
fen_river.build();
fen_nodes.build();
}
int query_nodes(int ar, int ac, int br, int bc)
{
int cnt = 0;
for (pair < int, int > cur : nodes)
{
if (cur.first >= ar && cur.first <= br &&
cur.second >= ac && cur.second <= bc)
cnt ++;
}
return cnt;
}
int query_hor_edges(int ar, int ac, int br, int bc)
{
int cnt = 0;
for (pair < int, int > cur : hor_edges)
{
if (cur.first >= ar && cur.first <= br &&
cur.second >= ac && cur.second <= bc)
cnt ++;
}
return cnt;
}
int query_ver_edges(int ar, int ac, int br, int bc)
{
int cnt = 0;
for (pair < int, int > cur : ver_edges)
{
if (cur.first >= ar && cur.first <= br &&
cur.second >= ac && cur.second <= bc)
cnt ++;
}
return cnt;
}
int query_river(int ar, int ac, int br, int bc)
{
int cnt = 0;
for (pair < int, int > cur : river)
{
if (cur.first >= ar && cur.first <= br &&
cur.second >= ac && cur.second <= bc)
cnt ++;
}
return cnt;
}
int colour(int ar, int ac, int br, int bc)
{
int V = fen_nodes.range_query(ar + 1, br, ac + 1, bc) + (br - ar + 2) * 2 + (bc - ac) * 2;
int E = 0;
E = E + query_hor_edges(ar + 1, ac, br, bc) + (bc - ac + 1) * 2;
E = E + query_ver_edges(ar, ac + 1, br, bc) + (br - ar + 1) * 2;
int C = 1;
if (ar < min_x && ac < min_y && br > max_x && bc > max_y)
C ++;
/// V + F = E + C + 1
/// F = E - V + C + 1
int F = E - V + C - fen_river.range_query(ar, br, ac, bc); //query_river(ar, ac, br, bc);
///cout << "V " << V << " E " << E << " C " << C << endl;
//cout << "Faces " << F << endl;
///exit(0);
return F;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
28 ms |
41304 KB |
Output is correct |
2 |
Correct |
41 ms |
41560 KB |
Output is correct |
3 |
Correct |
28 ms |
41304 KB |
Output is correct |
4 |
Correct |
30 ms |
41304 KB |
Output is correct |
5 |
Correct |
44 ms |
41560 KB |
Output is correct |
6 |
Correct |
26 ms |
41044 KB |
Output is correct |
7 |
Correct |
24 ms |
41048 KB |
Output is correct |
8 |
Correct |
25 ms |
41052 KB |
Output is correct |
9 |
Correct |
25 ms |
41080 KB |
Output is correct |
10 |
Correct |
25 ms |
41040 KB |
Output is correct |
11 |
Correct |
31 ms |
41304 KB |
Output is correct |
12 |
Correct |
38 ms |
41296 KB |
Output is correct |
13 |
Correct |
52 ms |
41820 KB |
Output is correct |
14 |
Correct |
67 ms |
41816 KB |
Output is correct |
15 |
Correct |
24 ms |
41048 KB |
Output is correct |
16 |
Correct |
26 ms |
41040 KB |
Output is correct |
17 |
Correct |
24 ms |
41048 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
26 ms |
41040 KB |
Output is correct |
2 |
Correct |
24 ms |
41048 KB |
Output is correct |
3 |
Execution timed out |
3029 ms |
173888 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
24 ms |
41048 KB |
Output is correct |
2 |
Correct |
923 ms |
184484 KB |
Output is correct |
3 |
Correct |
220 ms |
85016 KB |
Output is correct |
4 |
Correct |
489 ms |
139992 KB |
Output is correct |
5 |
Correct |
294 ms |
100260 KB |
Output is correct |
6 |
Correct |
115 ms |
50256 KB |
Output is correct |
7 |
Correct |
179 ms |
59012 KB |
Output is correct |
8 |
Correct |
730 ms |
153212 KB |
Output is correct |
9 |
Correct |
588 ms |
133280 KB |
Output is correct |
10 |
Correct |
113 ms |
52184 KB |
Output is correct |
11 |
Correct |
271 ms |
81216 KB |
Output is correct |
12 |
Correct |
899 ms |
184508 KB |
Output is correct |
13 |
Correct |
225 ms |
84816 KB |
Output is correct |
14 |
Correct |
482 ms |
140044 KB |
Output is correct |
15 |
Correct |
298 ms |
100384 KB |
Output is correct |
16 |
Correct |
111 ms |
48504 KB |
Output is correct |
17 |
Correct |
177 ms |
58960 KB |
Output is correct |
18 |
Correct |
334 ms |
88316 KB |
Output is correct |
19 |
Correct |
443 ms |
129252 KB |
Output is correct |
20 |
Correct |
567 ms |
145692 KB |
Output is correct |
21 |
Correct |
732 ms |
153272 KB |
Output is correct |
22 |
Correct |
593 ms |
133204 KB |
Output is correct |
23 |
Correct |
115 ms |
52048 KB |
Output is correct |
24 |
Correct |
273 ms |
81388 KB |
Output is correct |
25 |
Correct |
897 ms |
184544 KB |
Output is correct |
26 |
Correct |
219 ms |
84816 KB |
Output is correct |
27 |
Correct |
494 ms |
140248 KB |
Output is correct |
28 |
Correct |
301 ms |
100460 KB |
Output is correct |
29 |
Correct |
109 ms |
48440 KB |
Output is correct |
30 |
Correct |
176 ms |
59320 KB |
Output is correct |
31 |
Correct |
328 ms |
88476 KB |
Output is correct |
32 |
Correct |
445 ms |
129140 KB |
Output is correct |
33 |
Correct |
554 ms |
145932 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
28 ms |
41304 KB |
Output is correct |
2 |
Correct |
41 ms |
41560 KB |
Output is correct |
3 |
Correct |
28 ms |
41304 KB |
Output is correct |
4 |
Correct |
30 ms |
41304 KB |
Output is correct |
5 |
Correct |
44 ms |
41560 KB |
Output is correct |
6 |
Correct |
26 ms |
41044 KB |
Output is correct |
7 |
Correct |
24 ms |
41048 KB |
Output is correct |
8 |
Correct |
25 ms |
41052 KB |
Output is correct |
9 |
Correct |
25 ms |
41080 KB |
Output is correct |
10 |
Correct |
25 ms |
41040 KB |
Output is correct |
11 |
Correct |
31 ms |
41304 KB |
Output is correct |
12 |
Correct |
38 ms |
41296 KB |
Output is correct |
13 |
Correct |
52 ms |
41820 KB |
Output is correct |
14 |
Correct |
67 ms |
41816 KB |
Output is correct |
15 |
Correct |
24 ms |
41048 KB |
Output is correct |
16 |
Correct |
26 ms |
41040 KB |
Output is correct |
17 |
Correct |
24 ms |
41048 KB |
Output is correct |
18 |
Execution timed out |
3049 ms |
66068 KB |
Time limit exceeded |
19 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
28 ms |
41304 KB |
Output is correct |
2 |
Correct |
41 ms |
41560 KB |
Output is correct |
3 |
Correct |
28 ms |
41304 KB |
Output is correct |
4 |
Correct |
30 ms |
41304 KB |
Output is correct |
5 |
Correct |
44 ms |
41560 KB |
Output is correct |
6 |
Correct |
26 ms |
41044 KB |
Output is correct |
7 |
Correct |
24 ms |
41048 KB |
Output is correct |
8 |
Correct |
25 ms |
41052 KB |
Output is correct |
9 |
Correct |
25 ms |
41080 KB |
Output is correct |
10 |
Correct |
25 ms |
41040 KB |
Output is correct |
11 |
Correct |
31 ms |
41304 KB |
Output is correct |
12 |
Correct |
38 ms |
41296 KB |
Output is correct |
13 |
Correct |
52 ms |
41820 KB |
Output is correct |
14 |
Correct |
67 ms |
41816 KB |
Output is correct |
15 |
Correct |
24 ms |
41048 KB |
Output is correct |
16 |
Correct |
26 ms |
41040 KB |
Output is correct |
17 |
Correct |
24 ms |
41048 KB |
Output is correct |
18 |
Execution timed out |
3049 ms |
66068 KB |
Time limit exceeded |
19 |
Halted |
0 ms |
0 KB |
- |