// ~ Be Name Khoda ~
#include "rainbow.h"
#include<bits/stdc++.h>
//#pragma GCC optimize ("Ofast")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,O3")
using namespace std;
typedef long long ll;
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define fi first
#define se second
const int maxn = 1e6 + 10;
const int maxn5 = 2e5 + 10;
const int maxnt = 8e5 + 10;
const int maxn3 = 1e3 + 10;
const int mod = 1e9 + 7;
const ll inf = 1e18;
struct segment_tree{
vector <int> ini[maxn5], av[maxnt];
void build(int l, int r, int v){
if(r - l == 1){
sort(all(ini[l]));
for(auto u : ini[l])
av[v].pb(u);
return;
}
int mid = (l + r) >> 1;
build(l, mid, v * 2);
build(mid, r, v * 2 + 1);
int pt1 = 0, pt2 = 0;
while(pt1 < av[v * 2].size() || pt2 < av[v * 2 + 1].size()){
if(pt1 < av[v * 2].size() && (pt2 == av[v * 2 + 1].size() || av[v * 2][pt1] < av[v * 2 + 1][pt2]))
av[v].pb(av[v * 2][pt1++]);
else
av[v].pb(av[v * 2 + 1][pt2++]);
}
}
int get(int l, int r, int lq, int rq, int lq2, int rq2, int v){
if(rq <= l || r <= lq || lq2 >= rq2)
return 0;
if(lq <= l && r <= rq){
int pl = lower_bound(all(av[v]), lq2) - av[v].begin();
int pr = lower_bound(all(av[v]), rq2) - av[v].begin() - 1;
//cout << "asking for " << l << ' ' << r << ' ' << lq << ' ' << rq << ' ' << lq2 << ' ' << rq2 << ' ' << pl << ' ' << pr << ' ' << av[v].size() << endl;
return pr - pl + 1;
}
int mid = (l + r) >> 1;
return get(l, mid, lq, rq, lq2, rq2, v * 2) + get(mid, r, lq, rq, lq2, rq2, v * 2 + 1);
}
} segriv, segof, segam, segver;
int n, m;
vector <pair<int, int>> ver, riv;
vector <pair<pair<int, int>, pair<int, int>>> ed;
inline void add_edge(int x1, int yy1, int x2, int y2){
if(mp(x1, yy1) > mp(x2, y2)){
swap(x1, x2);
swap(yy1, y2);
}
ver.pb({x1, yy1});
ver.pb({x2, y2});
ed.pb({{x1, yy1}, {x2, y2}});
}
void init(int R, int C, int sr, int sc, int M, char *S){
n = R; m = C;
n++; m++;
sr--; sc--;
riv.pb({sr, sc});
add_edge(sr, sc, sr + 1, sc);
add_edge(sr, sc, sr, sc + 1);
add_edge(sr, sc + 1, sr + 1, sc + 1);
add_edge(sr + 1, sc, sr + 1, sc + 1);
for(int i = 0; i < M; i++){
if(S[i] == 'N')
sr--;
if(S[i] == 'S')
sr++;
if(S[i] == 'E')
sc++;
if(S[i] == 'W')
sc--;
riv.pb({sr, sc});
add_edge(sr, sc, sr + 1, sc);
add_edge(sr, sc, sr, sc + 1);
add_edge(sr, sc + 1, sr + 1, sc + 1);
add_edge(sr + 1, sc, sr + 1, sc + 1);
}
sort(all(riv)); sort(all(ver)); sort(all(ed));
riv.resize(unique(all(riv)) - riv.begin());
ver.resize(unique(all(ver)) - ver.begin());
ed.resize(unique(all(ed)) - ed.begin());
for(auto [x, y] : riv){
segriv.ini[x].pb(y);
//cout << "river of " << x << ' ' << y << endl;
}
for(auto [x, y] : ver)
segver.ini[x].pb(y);
for(auto [p1, p2] : ed){
if(p1.fi == p2.fi)
segof.ini[p1.fi].pb(min(p1.se, p2.se));
else
segam.ini[min(p1.fi, p2.fi)].pb(p1.se);
}
segriv.build(0, n, 1);
segver.build(0, n, 1);
segof.build(0, n, 1);
segam.build(0, n, 1);
}
int colour(int ax, int ay, int bx, int by){
ax--; ay--; bx--; by--;
ll nover = 4 + 2 * (bx - ax + by - ay), noed = 2 * (bx - ax + by - ay + 2), noriv = 0;
for(auto [x, y] : riv)
noriv += (ax <= x && x <= bx && ay <= y && y <= by);
for(auto [x, y] : ver)
nover += (ax < x && x < bx + 1 && ay < y && y < by + 1);
for(auto [p1, p2] : ed){
int cnt = 0;
if(ax < p1.fi && p1.fi < bx + 1 && ay < p1.se && p1.se < by + 1)
cnt += 0;
else if(ax <= p1.fi && p1.fi <= bx + 1 && ay <= p1.se && p1.se <= by + 1)
cnt++;
else
cnt += 10;
if(ax < p2.fi && p2.fi < bx + 1 && ay < p2.se && p2.se < by + 1)
cnt += 0;
else if(ax <= p2.fi && p2.fi <= bx + 1 && ay <= p2.se && p2.se <= by + 1)
cnt++;
else
cnt += 10;
noed += (cnt < 2);
}
/*
if(ax < bx && ay < by)
nover += segver.get(0, n, ax + 1, bx + 1, ay + 1, by + 1, 1);
if(ax < bx)
noed += segof.get(0, n, ax + 1, bx + 1, ay, by + 1, 1);
if(ay < by)
noed += segam.get(0, n, ax, bx + 1, ay + 1, by + 1, 1);
noriv = segriv.get(0, n, ax, bx + 1, ay, by + 1, 1);
*/
//cout << "ok " << noed << ' ' << noriv << ' ' << nover << endl;
return noed - nover + 1 - noriv;
}
/*
6 4 9 1
3 3
NWESSWEWS
1 2 5 3
2 3 2 3
3 2 4 4
5 3 6 4
*/
Compilation message
rainbow.cpp: In member function 'void segment_tree::build(int, int, int)':
rainbow.cpp:41:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
41 | while(pt1 < av[v * 2].size() || pt2 < av[v * 2 + 1].size()){
| ~~~~^~~~~~~~~~~~~~~~~~
rainbow.cpp:41:45: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
41 | while(pt1 < av[v * 2].size() || pt2 < av[v * 2 + 1].size()){
| ~~~~^~~~~~~~~~~~~~~~~~~~~~
rainbow.cpp:42:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | if(pt1 < av[v * 2].size() && (pt2 == av[v * 2 + 1].size() || av[v * 2][pt1] < av[v * 2 + 1][pt2]))
| ~~~~^~~~~~~~~~~~~~~~~~
rainbow.cpp:42:47: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | if(pt1 < av[v * 2].size() && (pt2 == av[v * 2 + 1].size() || av[v * 2][pt1] < av[v * 2 + 1][pt2]))
| ~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
49 ms |
94284 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
47 ms |
94140 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
45 ms |
94220 KB |
Output is correct |
| 2 |
Correct |
233 ms |
155428 KB |
Output is correct |
| 3 |
Correct |
357 ms |
190336 KB |
Output is correct |
| 4 |
Correct |
293 ms |
178676 KB |
Output is correct |
| 5 |
Correct |
249 ms |
159800 KB |
Output is correct |
| 6 |
Correct |
181 ms |
118080 KB |
Output is correct |
| 7 |
Incorrect |
212 ms |
128176 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
49 ms |
94284 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
49 ms |
94284 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
