#include <bits/stdc++.h>
#include "rainbow.h"
using namespace std;
vector<pair<int,int>> pts;
struct segtr{
vector<int> t;
int n;
void init(int s){
n = s;
t.assign((s + 1) * 4,0);
}
void upd(int pos,int val,int v,int tl,int tr){
t[v] += val;
if(tl == tr){
return;
}
int tm = (tl + tr) >> 1;
if(pos <= tm) upd(pos,val,v+v,tl,tm);
else upd(pos,val,v+v+1,tm+1,tr);
}
int get(int l,int r,int v,int tl,int tr){
if(l > r || tl >r || l > tr) return 0;
if(tl >= l && tr <= r) return t[v];
int tm = (tl + tr) >> 1;
return get(l,r,v+v,tl,tm) + get(l,r,v+v+1,tm+1,tr);
}
};
struct dd{
vector<vector<int>> f,t;
vector<segtr> b;
int n;
void build(int v,int tl,int tr){
if(tl == tr){
t[v] = f[tl];
t[v].resize(unique(t[v].begin(),t[v].end()) - t[v].begin());
// cerr << (int)t[v].size() << '\n';
b[v].init((int)t[v].size());
}else{
int tm = (tl + tr) >> 1;
build(v+v,tl,tm);
build(v + v + 1,tm + 1,tr);
t[v].resize((int)t[v+v].size() + (int)t[v +v + 1].size());
merge(t[v + v].begin(),t[v + v].end(),t[v + v + 1].begin(),t[v + v + 1].end(),t[v].begin());
t[v].resize(unique(t[v].begin(),t[v].end()) - t[v].begin());
b[v].init((int)t[v].size());
}
}
void init(int s,vector<vector<int>> _f){
n = s;
t.resize((n + 1) * 4);
b.resize((n+1)*4);
f = _f;
build(1,1,n);
}
void upd(int x,int y,int val,int v,int tl,int tr){
int it = lower_bound(t[v].begin(),t[v].end(),y)-t[v].begin()+1;
b[v].upd(it,val,1,1,b[v].n);
if(tl == tr) return;
int tm = (tl + tr) >> 1;
if(x <= tm) upd(x,y,val,v+v,tl,tm);
else upd(x,y,val,v+v+1,tm+1,tr);
}
int get(int l,int r,int l1,int r1,int v,int tl,int tr){
// return 0;
if(l > r || tl > r || l > tr) return 0;
if(tl >= l && tr <= r){
int it = lower_bound(t[v].begin(),t[v].end(),l1)-t[v].begin()+1;
int it1 = upper_bound(t[v].begin(),t[v].end(),r1)-t[v].begin();
return b[v].get(it,it1,1,1,b[v].n);
}
int tm =(tl+tr)>>1;
return get(l,r,l1,r1,v+v,tl,tm)+get(l,r,l1,r1,v+v+1,tm+1,tr);
}
}ver,bf,uu,ll;
map<pair<int,int>,int>in;
void init(int R, int C, int sr, int sc, int M, char *S) {
pts.push_back({sr,sc});
vector<vector<int>> f(R+1);
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{
sc++;
}
assert(sr <= R && sr >= 1);
assert(sc <= C && sc >= 1);
pts.push_back({sr,sc});
in[{sr,sc}]=1;
}
sort(pts.begin(),pts.end());
pts.resize(unique(pts.begin(),pts.end()) - pts.begin());
for(auto [x,y]:pts){
f[x].push_back(y);
}
ver.init(R,f);
bf.init(R,f);
uu.init(R,f);ll.init(R,f);
for(auto [x,y]:pts){
if(in.count({x+1,y})&&in.count({x,y+1})&&in.count({x+1,y+1})){
bf.upd(x,y,1,1,1,bf.n);
}
if(in.count({x-1,y}))
{
uu.upd(x,y,1,1,1,uu.n);
}
if(in.count({x,y-1})){
ll.upd(x,y,1,1,1,ll.n);
}
ver.upd(x,y,1,1,1,ver.n);
}
}
const int dx[] = {1,0,-1,0},dy[] = {0,1,0,-1};
map<pair<int,int>,bool> k,vis;
int colour(int ar, int ac, int br, int bc) {
k.clear();
vis.clear();
int E = 0;
for(auto [r,c]:pts){
if(r >= ar && r <= br && c >= ac && c <= bc){
k[{r,c}] = 1;
}
}
for(int i = ar - 1;i <= br + 1;i++){
k[{i,ac-1}] = k[{i,bc+1}] = 1;
}
for(int i = ac - 1;i <= bc + 1;i++){
k[{ar-1,i}] = k[{br+1,i}] = 1;
}
int _bf = 0,tt = 0;;
for(auto [xx,_y]:k){
auto [r,c] = xx;
if(k.count({r + 1,c}) && k.count({r,c + 1}) && k.count({r + 1,c + 1})){
tt++;
}
if(k.count({r+1,c+1}) && !k.count({r+1,c}) && !k.count({r,c+1})){
E += 1;
}
if(k.count({r+1,c-1}) && !k.count({r+1,c}) && !k.count({r,c-1})){
E += 1;
}
if(!vis.count({r,c})){
queue<pair<int,int>> q;
q.push({r,c});
vis[{r,c}]=1;
while(!q.empty()){
auto [x,y] = q.front();q.pop();
// cout << x << ' ' << y << '\n';
for(int i = 0;i < 4;i++){
int _x = x + dx[i],_y = y + dy[i];
// if(k.count({_x,_y})){
// E++;
// }
if(k.count({_x,_y}) && !vis.count({_x,_y})){
vis[{_x,_y}]=1;
q.push({_x,_y});
}
}
}
}
}
int val =ver.get(ar,br,ac,bc,1,1,ver.n);
int bord_sum =(br-ar+3)*2+(bc-ac+1)*2;
bool ok = false;
int _ = ver.get(ar,ar,ac,bc,1,1,ver.n)+ver.get(ar,br,bc,bc,1,1,ver.n)+ver.get(ar,br,ac,ac,1,1,ver.n)+ver.get(br,br,ac,bc,1,1,ver.n);
if(val > 0 && _==0){
ok=1;
}
_bf = (in.count({ar,ac})) + (in.count({ar,bc}))+(in.count({br,ac})) + (in.count({br,bc})) + bf.get(ar,br-1,ac,bc-1,1,1,bf.n);
_bf += ll.get(ar,ar,ac+1,bc,1,1,ll.n)+ll.get(br,br,ac+1,bc,1,1,ll.n);
_bf += uu.get(ar+1,br,ac,ac,1,1,uu.n)+uu.get(ar+1,br,bc,bc,1,1,uu.n);
E += (ll.get(ar,br,ac+1,bc,1,1,ll.n) + uu.get(ar+1,br,ac,bc,1,1,uu.n)) + _;
return -val+ E - tt + 1+ok;
}
Compilation message
rainbow.cpp: In function 'int colour(int, int, int, int)':
rainbow.cpp:169:9: warning: unused variable 'bord_sum' [-Wunused-variable]
169 | int bord_sum =(br-ar+3)*2+(bc-ac+1)*2;
| ^~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
348 KB |
Output is correct |
| 2 |
Correct |
111 ms |
880 KB |
Output is correct |
| 3 |
Correct |
79 ms |
604 KB |
Output is correct |
| 4 |
Correct |
84 ms |
604 KB |
Output is correct |
| 5 |
Correct |
164 ms |
856 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Execution timed out |
3057 ms |
67204 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
899 ms |
438084 KB |
Output is correct |
| 3 |
Correct |
779 ms |
345636 KB |
Output is correct |
| 4 |
Incorrect |
827 ms |
384828 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
348 KB |
Output is correct |
| 2 |
Correct |
111 ms |
880 KB |
Output is correct |
| 3 |
Correct |
79 ms |
604 KB |
Output is correct |
| 4 |
Correct |
84 ms |
604 KB |
Output is correct |
| 5 |
Correct |
164 ms |
856 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
348 KB |
Output is correct |
| 2 |
Correct |
111 ms |
880 KB |
Output is correct |
| 3 |
Correct |
79 ms |
604 KB |
Output is correct |
| 4 |
Correct |
84 ms |
604 KB |
Output is correct |
| 5 |
Correct |
164 ms |
856 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
