#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;
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});
}
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);
for(auto [x,y]:pts){
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 V = 0,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;
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})){
bf++;
}
if(k.count({r+1,c+1}) && !k.count({r+1,c}) && !k.count({r,c+1})){
E += 2;
}
if(k.count({r+1,c-1}) && !k.count({r+1,c}) && !k.count({r,c-1})){
E += 2;
}
if(!vis.count({r,c})){
queue<pair<int,int>> q;
q.push({r,c});
vis[{r,c}]=1;
while(!q.empty()){
V++;
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});
}
}
}
}
}
assert(E%2==0);
E /= 2;
int val =ver.get(ar,br,ac,bc,1,1,ver.n);
bool ok = false;
if(val > 0 && ver.get(ar,ar,ac,ac,1,1,ver.n)==0 && ver.get(ar,ar,bc,bc,1,1,ver.n)==0
&& ver.get(br,br,ac,ac,1,1,ver.n)==0 && ver.get(br,br,bc,bc,1,1,ver.n)==0
){
ok=1;
}
return -val-(br-ar+3)*2-(bc-ac+1)*2 + E - bf + 1+ok;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
41 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Execution timed out |
3095 ms |
56108 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
671 ms |
141932 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
41 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
41 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
