/*#include "rainbow.h"
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
void init(int R, int C, int sr, int sc, int M, char *S) {
n=R;
m=C;
x=sr;
y=sc;
p[1]={x,y};
mp[p[1]]=2;
for(i=2;i<=M+1;i++)
{
c=S[i];
if(c=='N')
{
dx=-1;
dy=0;
}
if(c=='E')
{
dx=0;
dy=1;
}
if(c=='S')
{
dx=1;
dy=0;
}
if(c=='W')
{
dx=0;
dy=-1;
}
x+=dx;
y+=dy;
p[i]={x,y};
mp[p[i]]=2;
}
swap(n,m);
m=M+1;
for(i=1;i<=m;i++)
{
for(j=0;j<8;j++)
{
q={p[i].first+ddx[j],p[i].second+ddy[j]};
if(mp[q])
continue;
mp[q]=1;
v.push_back(q);
}
}
for(i=0;i<v.size();i++)
{
q=v[i];
if(c[q])
continue;
while(1)
{
if(c[q]==1)
break;
c[q]=1;
add(q);
x=mp[{q.first-1,q.second}];
y=mp[{q.first,q.second+1}];
z=mp[{q.first+1,q.second}];
w=mp[{q.first,q.second-1}];
x=f(x); y=f(y); z=f(z); w=f(w);
dx=px[x][y][z][w][prv];
dy=py[x][y][z][w][prv];
prv=pp[x][y][z][w][prv];
pq={q.first+dx,q.second+dy};
add_edge(q,pq);
q=pq;
}
}
}
int colour(int ar, int ac, int br, int bc) {
l=ar;
r=ac;
return g1(1,262144,1,br,bc)-g2(1,262144,1,br,bc);
}
*/
#include "rainbow.h"
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
ll n,m,i,j,l,r,x,y,z,w,s,t,cc[1100000],dx,dy,ddx[11000],ddy[11000],dddx[11000],dddy[110000];
char c;
pair<ll,ll> p[1100000],q;
map<pair<ll,ll>,ll> mp,mpp;
vector<ll> v[1100000];
vector<pair<ll,ll>> u;
void init(int R, int C, int sr, int sc, int M, char *S) {
ddx[0]=1; ddy[0]=0;
ddx[1]=1; ddy[1]=1;
ddx[2]=1; ddy[2]=-1;
ddx[3]=0; ddy[3]=1;
ddx[4]=0; ddy[4]=-1;
ddx[5]=-1; ddy[5]=1;
ddx[6]=-1; ddy[6]=0;
ddx[7]=-1; ddy[7]=-1;
n=R;
m=C;
x=sr;
y=sc;
p[1]={x,y};
mp[p[1]]=2;
for(i=2;i<=M+1;i++)
{
c=S[i-2];
if(c=='N')
{
dx=-1;
dy=0;
}
if(c=='E')
{
dx=0;
dy=1;
}
if(c=='S')
{
dx=1;
dy=0;
}
if(c=='W')
{
dx=0;
dy=-1;
}
x+=dx;
y+=dy;
p[i]={x,y};
//printf("[%lld,%lld]\n",p[i].first,p[i].second);
mp[p[i]]=2;
}
swap(n,m);
m=M+1;
for(i=1;i<=m;i++)
{
for(j=0;j<8;j++)
{
q={p[i].first+ddx[j],p[i].second+ddy[j]};
if(mp[q])
continue;
mp[q]=1;
u.push_back(q);
}
}
for(i=0;i<u.size();i++)
{
// printf("(%lld %lld %lld)\n",i,u[i].first,u[i].second);
mpp[u[i]]=i;
}
dddx[0]=1; dddy[0]=0;
dddx[1]=-1; dddy[1]=0;
dddx[2]=0;
dddy[2]=1;
dddx[3]=0;
dddy[3]=-1;
for(i=0;i<u.size();i++)
{
x=u[i].first;
y=u[i].second;
for(j=0;j<4;j++)
{
if(mp[{x+dddx[j],y+dddy[j]}]==1)
{
v[i].push_back(mpp[{x+dddx[j],y+dddy[j]}]);
}
}
}
}
ll ok(pair<ll,ll> p,ll x,ll y,ll z,ll w)
{
if(x<=p.first&&p.first<=z&&y<=p.second&&p.second<=w)
return 1;
else
return 0;
}
void f(ll x,ll ar,ll ac,ll br,ll bc)
{
ll i;
cc[x]=1;
for(i=0;i<v[x].size();i++)
{
if(cc[v[x][i]]==0&&ok(u[v[x][i]],ar,ac,br,bc))
f(v[x][i],ar,ac,br,bc);
}
}
int colour(int ar, int ac, int br, int bc) {
s=0;
for(i=0;i<u.size();i++)
{
cc[i]=0;
}
for(i=0;i<u.size();i++)
{
if(cc[i]==0&&ok(u[i],ar,ac,br,bc))
{
// printf("(%lld,%lld,%lld)\n",i,u[i].first,u[i].second);
s++;
f(i,ar,ac,br,bc);
}
}
return s;
}
Compilation message
rainbow.cpp: In function 'void init(int, int, int, int, int, char*)':
rainbow.cpp:151:14: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
151 | for(i=0;i<u.size();i++)
| ~^~~~~~~~~
rainbow.cpp:162:14: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
162 | for(i=0;i<u.size();i++)
| ~^~~~~~~~~
rainbow.cpp: In function 'void f(ll, ll, ll, ll, ll)':
rainbow.cpp:186:14: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
186 | for(i=0;i<v[x].size();i++)
| ~^~~~~~~~~~~~
rainbow.cpp: In function 'int colour(int, int, int, int)':
rainbow.cpp:194:14: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
194 | for(i=0;i<u.size();i++)
| ~^~~~~~~~~
rainbow.cpp:198:14: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
198 | for(i=0;i<u.size();i++)
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
29272 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
29276 KB |
Output is correct |
| 2 |
Correct |
8 ms |
29276 KB |
Output is correct |
| 3 |
Execution timed out |
3080 ms |
63544 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
29276 KB |
Output is correct |
| 2 |
Correct |
493 ms |
87036 KB |
Output is correct |
| 3 |
Correct |
366 ms |
87072 KB |
Output is correct |
| 4 |
Correct |
350 ms |
84572 KB |
Output is correct |
| 5 |
Correct |
287 ms |
72580 KB |
Output is correct |
| 6 |
Incorrect |
64 ms |
32752 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
29272 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
29272 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
