#include "rainbow.h"
#include <bits/stdc++.h>
#define f first
#define s second
#define m_p make_pair
#define vec vector
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define sz(x) (int)(x).size()
#define pw(x) (1LL<<(x))
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
typedef long double ld;
template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
const int tx[4]={1,-1,0,0};
const int ty[4]={0,0,1,-1};
const char wow[4]={'N','S','E','W'};
const int N=2e5+3;
struct fenwick{
vec<int> a;
vec<int> fen;
void build(){
sort(all(a));
a.erase(unique(all(a)),a.end());
fen.assign(sz(a)+1,0);
}
void upd(int i,int x){
int id=i;
i=lower_bound(all(a),i)-a.begin();
assert(id==a[i]);
++i;
while(i<sz(fen)){
fen[i]+=x;
i+=i&-i;
}
}
int get(int i){
i=upper_bound(all(a),i)-a.begin()-1;
++i;
int ans=0;
while(i>0){
ans+=fen[i];
i-=i&-i;
}
// cout<<"LOS "<<ans<<endl;
return ans;
}
int get(int l,int r){
return get(r)-get(l-1);
}
};
struct _2d{
fenwick fnw[N];
vec<pii> w;
void add(int i,int x){
w.pb({i,x});
++i;
while(i<N){
fnw[i].a.pb(x);
i+=i&-i;
}
}
void upd(int i,int j,int x){
++i;
while(i<N){
fnw[i].upd(j,x);
i+=i&-i;
}
}
void build(){
for(int i=0;i<N;i++)
fnw[i].build();
for(auto &z : w)
upd(z.f,z.s,1);
}
int get(int i,int l,int r){
++i;
int ans=0;
while(i>0){
ans+=fnw[i].get(l,r);
i-=i&-i;
}
return ans;
}
int get(int l1,int r1,int l,int r){
if(l1>r1 || l>r)
return 0;
return get(r1,l,r)-get(l1-1,l,r);
}
}x,y,kv,pt;
void init(int n,int m, int sr, int sc, int l, char *S) {
vec<pii> here;
here.pb({sr,sc});
for(int i=0;i<l;i++){
int j=find(wow,wow+4,S[i])-wow;
sr+=tx[j];sc+=ty[j];
here.pb({sr,sc});
// cout<<"W "<<sr<<' '<<sc<<endl;
}
sort(all(here));here.erase(unique(all(here)),here.end());
vec<pii> w1,w2;
auto check=[&](pii p){
return binary_search(all(here),p);
};
for(auto &z : here){
// cout<<"P "<<z.f<<' '<<z.s<<endl;
if(check(m_p(z.f-1,z.s))){
x.add(z.f,z.s);
}
if(check(m_p(z.f,z.s-1))){
y.add(z.f,z.s);
}
pt.add(z.f,z.s);
if(check(m_p(z.f,z.s-1)) && check(m_p(z.f-1,z.s-1)) && check(m_p(z.f-1,z.s))){
kv.add(z.f,z.s);
}
}
kv.build();pt.build();x.build();y.build();
}
int colour(int ar, int ac, int br, int bc) {
swap(ac,br);
if(ar==ac){
return br-bc+1-pt.get(ar,ac,br,bc);
}
if(br==bc){
return ar-ac+1-pt.get(ar,ac,br,bc);
}
// if(!pt.get(ar,ac,br,bc))
int e=x.get(ar+1,ac,br,bc)+y.get(ar,ac,br+1,bc);
int v=pt.get(ar,ac,br,bc);
if(!v){
return 1;
}
/// edges between от рамки
e+=pt.get(ar,ar,br,bc)+pt.get(ac,ac,br,bc)+(bc-br+2)*2+(ar-ac+2)*2+4;
e+=pt.get(ar,ac,br,br)+pt.get(ar,ac,bc,bc);
///
v+=2*(bc-br+2)+(ar-ac+2)*2+4;
int f=e-v+3-((pt.get(ar,ar,br,bc)>0 && pt.get(ac,ac,br,bc)>0) || (pt.get(ar,ac,br,br)>0 && pt.get(ar,ac,bc,bc)>0));
f-=kv.get(ar+1,ac,br+1,bc);
/// delete квадраты с рамкой
f-=x.get(ar+1,ac,br,br);
f-=x.get(ar+1,ac,bc,bc);
f-=y.get(ar,ar,br+1,bc);
f-=y.get(ac,ac,br+1,bc);
f-=pt.get(ar,ar,bc,bc);
f-=pt.get(ac,ac,bc,bc);
f-=pt.get(ar,ar,br,br);
f-=pt.get(ac,ac,br,br);
--f;
// cout<<"HERE "<<e<<' '<<v<<' '<<f<<endl;
return f;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
52 ms |
62980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
55 ms |
62852 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
56 ms |
62832 KB |
Output is correct |
| 2 |
Correct |
230 ms |
85860 KB |
Output is correct |
| 3 |
Runtime error |
53 ms |
78664 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
52 ms |
62980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
52 ms |
62980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
