#include "rainbow.h"
#include<bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
template <typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template <typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}
int readint(){
int x=0,f=1; char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
namespace perst{
int root[200005],son[5000005][2],sum[500005],tsz;
void modify(int&x,int f,int l,int r,int p,int v){
x=++tsz; son[x][0]=son[f][0]; son[x][1]=son[f][1]; sum[x]=sum[f]+v;
if(l==r) return;
int mid=(l+r)/2;
if(p<=mid) modify(son[x][0],son[f][0],l,mid,p,v);
else modify(son[x][1],son[f][1],mid+1,r,p,v);
}
void modify(int x,int y,int v){modify(root[x],root[x],1,200000,y,v);}
int ask(int x,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr) return sum[x];
int mid=(l+r)/2;
if(qr<=mid) return ask(son[x][0],l,mid,ql,qr);
else if(ql>mid) return ask(son[x][1],mid+1,r,ql,qr);
else return ask(son[x][0],l,mid,ql,qr)+ask(son[x][1],mid+1,r,ql,qr);
}
int query(int x1,int x2,int y1,int y2){return ask(root[x2],1,200000,y1,y2)-ask(root[x1-1],1,200000,y1,y2);}
};
int mat[55][55],lx,ly,rx,ry;
vector<int> qs[55];
void init(int r,int c,int sc,int sr,int m,char* s){
mat[sc][sr]=1;
lx=rx=sc;
ly=ry=sr;
qs[sc].pb(sr);
for(int i=0;i<m;i++){
if(s[i]=='N') sc--;
if(s[i]=='S') sc++;
if(s[i]=='E') sr++;
if(s[i]=='W') sr--;
mat[sc][sr]=1;
lx=min(lx,sc);
rx=max(rx,sc);
ly=min(ly,sr);
ry=max(ry,sr);
qs[sc].pb(sr);
}
for(int i=1;i<=r;i++){
perst::root[i]=perst::root[i-1];
sort(qs[i].begin(),qs[i].end());
qs[i].erase(unique(qs[i].begin(),qs[i].end()),qs[i].end());
for(int j:qs[i]){
cout<<i<<" "<<j<<endl;
perst::modify(i,j,1);
}
}
}
int colour(int x1,int y1,int x2,int y2){
int res=0;
if(x1<lx&&rx<x2&&y1<ly&&ry<y2) res=1;
res+=(x2-x1+1)*(y2-y1+1)-perst::query(x1,x2,y1,y2);
for(int i=x1;i<=x2;i++) for(int j=y1;j<=y2;j++){
if(mat[i][j]==1) continue;
if(i+1<=x2&&mat[i+1][j]==0) res--;
if(j+1<=y2&&mat[i][j+1]==0) res--;
if(i+1<=x2&&j+1<=y2&&mat[i+1][j]==0&&mat[i][j+1]==0&&mat[i+1][j+1]==0) res++;
}
return res;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
