#include "rainbow.h"
#include<bits/stdc++.h>
#define lf double
#define ll long long
#define cc pair<char,char>
#define ull unsigned ll
#define ii pair<int,int>
#define li pair<ll,int>
#define iii pair<ii,int>
#define iiii pair<ii,ii>
#define iiii2 pair<int,iii>
#define lii pair<ll,ii>
#define lolo pair<ll,ll>
#define heap priority_queue
#define mp make_pair
#define st first
#define nd second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) x.begin(),x.end()
#define len(x) strlen(x)
#define sz(x) (int) x.size()
#define orta ((bas+son)/2)
#define min3(x,y,z) min(min(x,y),z)
#define max3(x,y,z) max(max(x,y),z)
#define umin(x,y) x=min(x,y)
#define umax(x,y) x=max(x,y)
#define dbgs(x) cerr<<(#x)<<" --> "<<(x)<<" "
#define dbg(x) cerr<<(#x)<<" --> "<<(x)<<endl;getchar()
#define MOD 1000000007
#define inf 4000000000000000000ll
#define MAXN 200005
#define LOG 20
#define magic 100
#define KOK 350
#define EPS 0.0025
#define pw(x) ((1ll)<<(x))
#define PI 3.1415926535
using namespace std;
struct seg {
int pre;
int suf;
int ins;
int full;
} Sg[MAXN*4];
int lazy[MAXN*4];
int reg,R,C;
int bol[55][MAXN],nxt[3][MAXN],prv[3][MAXN];
bool vis[55][MAXN],a[55][MAXN];
vector<iii> qu[MAXN];
vector<int> eve[MAXN];
int w[4][2]={1,0,0,1,-1,0,0,-1};
void inc(int &x,int &y,char c) {
if(c=='N') x--;
if(c=='S') x++;
if(c=='W') y--;
if(c=='E') y++;
}
void clear() {
memset(vis,0,sizeof(vis));
memset(bol,0,sizeof(bol));
reg=0;
}
void push(int node) {
lazy[node*2]=lazy[node];
lazy[node*2+1]=lazy[node];
lazy[node]=0;
}
seg merge(seg x,seg y) {
seg res;
res.pre=x.pre+(x.full)*y.pre;
res.suf=y.suf+(y.full)*x.suf;
res.full=(x.full&y.full);
res.ins=x.ins+y.ins+(x.suf>0 && y.pre>0 && !x.full && !y.full);
return res;
}
seg get(int node,int bas,int son,int x,int y,int flag) {
if(bas>y || son<x) return {0,0,0,1};
if(bas>=x && son<=y) {
if(flag==1) return {son-bas+1,son-bas+1,0,1};
if(flag==2) return {0,0,0,0};
return Sg[node];
}
if(!flag) flag=lazy[node];
return merge(get(node*2,bas,orta,x,y,flag),get(node*2+1,orta+1,son,x,y,flag));
}
void up(int node,int bas,int son,int x,int y,int val) {
if(bas>y || son<x) return ;
if(bas>=x && son<=y) {
lazy[node]=val;
return ;
}
push(node);
up(node*2,bas,orta,x,y,val);
up(node*2+1,orta+1,son,x,y,val);
if(lazy[node*2]==2 && lazy[node*2+1]==2) {
Sg[node].pre=0;
Sg[node].suf=0;
Sg[node].ins=0;
}
else if(lazy[node*2]==2) {
Sg[node].pre=0;
Sg[node].suf=Sg[node*2+1].suf;
Sg[node].ins=Sg[node*2+1].ins+(Sg[node*2+1].pre>0);
}
else if(lazy[node*2+1]==2) {
Sg[node].pre=Sg[node*2].pre;
Sg[node].suf=0;
Sg[node].ins=Sg[node*2].ins+(Sg[node*2].suf>0);
}
else {
Sg[node]=merge(Sg[node*2],Sg[node*2+1]);
}
}
void build(int node,int bas,int son) {
if(bas==son) {
Sg[node]={1,1,0,1};
return ;
}
build(node*2,bas,orta);
build(node*2+1,orta+1,son);
Sg[node]=merge(Sg[node*2],Sg[node*2+1]);
}
void dfs(int x,int y,int lx,int ly,int rx,int ry) {
if(vis[x][y] || a[x][y]) return ;
if(x>rx || x<lx || y>ry || y<ly) return ;
bol[x][y]=reg;
vis[x][y]=1;
for(int i=0;i<4;i++) dfs(x+w[i][0],y+w[i][1],lx,ly,rx,ry);
}
void fillnaive(int R,int C,int sr,int sc,int M,char *S) {
a[sr][sc]=1;
for(int i=0;i<M;i++) {
inc(sr,sc,S[i]);
a[sr][sc]=1;
}
if(R==2) {
clear();
for(int i=1;i<=R;i++) {
for(int j=1;j<=C;j++) {
if(!vis[i][j] && !a[i][j]) {
reg++;
dfs(i,j,1,1,R,C);
}
}
}
for(int i=1;i<=R;i++) {
for(int j=C;j>=1;j--) {
if(bol[i][j]) nxt[i][j]=j;
else nxt[i][j]=nxt[i][j+1];
}
for(int j=1;j<=C;j++) {
if(bol[i][j]) prv[i][j]=j;
else prv[i][j]=prv[i][j-1];
}
}
}
}
void init(int R, int C, int sr, int sc, int M, char *S) {
::R=R;
::C=C;
if((R<=50 && C<=50) || R<=2) {
fillnaive(R,C,sr,sc,M,S);
}
else {
eve[sr].pb(sc);
for(int i=0;i<M;i++) {
inc(sr,sc,S[i]);
eve[sr].pb(sc);
}
for(int i=1;i<MAXN;i++) {
eve[i].erase(unique(all(eve[i])),eve[i].end());
if(!sz(eve[i])) {
qu[i].pb({{0,MAXN-1},0});
continue ;
}
qu[i].pb({{0,eve[i][0]-1},0});
for(int j=0;j<sz(eve[i]);j++) {
int bas=j;
while(j+1<sz(eve[i]) && eve[i][j]==eve[i][j+1]) j++;
qu[i].pb({{eve[i][bas],eve[i][j]},1});
if(j+1<sz(eve[i])) {
qu[i].pb({{eve[i][j]+1,eve[i][j+1]-1},0});
}
else {
qu[i].pb({{eve[i][j]+1,MAXN-1},0});
}
}
}
}
}
int colour(int ar, int ac, int br, int bc) {
if(R<=50 && C<=50) {
clear();
for(int i=ar;i<=br;i++) {
for(int j=ac;j<=bc;j++) {
if(!vis[i][j] && !a[i][j]) {
reg++;
dfs(i,j,ar,ac,br,bc);
}
}
}
return reg;
}
if(R<=2) {
int r1=min(nxt[ar][ac],nxt[br][ac]);
int r2=max(prv[br][bc],prv[ar][bc]);
return r2-r1+1;
}
build(1,ac,bc);
lazy[1]=1;
int res=0;
for(int i=ar;i<=br;i++) {
for(iii j:qu[i]) {
if(j.st.nd<ac || j.st.st>bc) continue ;
int l=max(j.st.st,ac);
int r=min(j.st.nd,bc);
if(j.nd) {
seg query=get(1,ac,bc,l,r,0);
res+=query.ins+(query.pre>0)+(query.suf>0)-(query.pre && query.suf && query.pre==query.suf);
}
up(1,ac,bc,l,r,j.nd+1);
}
}
return res;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3006 ms |
63736 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
172 ms |
63736 KB |
Output is correct |
| 2 |
Correct |
154 ms |
63736 KB |
Output is correct |
| 3 |
Incorrect |
155 ms |
89300 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
52 ms |
89300 KB |
Output is correct |
| 2 |
Incorrect |
77 ms |
89300 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3006 ms |
63736 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3006 ms |
63736 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
