#include <bits/stdc++.h>
#include "rainbow.h"
using namespace std;
const int nmax = 2e5;
int R, C;
map<int,bool> fr[nmax + 5];
map<int,int> r_nod[nmax + 5];
vector<int> lr[nmax + 5], lc[nmax + 5];
vector<pair<int,int>> sr[nmax + 5], sc[nmax + 5];
set<pair<int,int>> sv;
int t[5 * nmax + 5], rang[5 * nmax + 5];
int Min_r[5 * nmax + 5], Min_c[5 * nmax + 5], Max_r[5 * nmax + 5], Max_c[5 * nmax + 5];
vector<int> l_nod;
bool sel[5 * nmax + 5];
int nr_nod = 0;
int dr[] = {0,0,1,-1,1,1,-1,-1};
int dc[] = {1,-1,0,0,-1,1,-1,1};
int rep(int x)
{
if(t[x] == x)
{
return x;
}
return (t[x] = rep(t[x]));
}
void uneste(int x, int y)
{
x = rep(x);
y = rep(y);
if(x == y)
{
return;
}
if(rang[x] < rang[y])
{
swap(x,y);
}
Min_r[x] = min(Min_r[x], Min_r[y]);
Max_r[x] = max(Max_r[x], Max_r[y]);
Min_c[x] = min(Min_c[x], Min_c[y]);
Max_c[x] = max(Max_c[x], Max_c[y]);
rang[x] += rang[y];
t[y] = x;
}
void Add(int r, int c)
{
for(int p=0;p<4;p++)
{
int rr = r + dr[p];
int cc = c + dc[p];
if(rr >= 0 && cc >= 0 && r_nod[rr][cc])
{
uneste(r_nod[rr][cc], r_nod[r][c]);
}
}
}
void init(int RR, int CC, int r, int c, int m, char *s)
{
R = RR;
C = CC;
fr[r][c] = true;
lr[r].push_back(c);
lc[c].push_back(r);
vector<pair<int,int>> l;
l.push_back({r,c});
int Max_r_riv = r;
for(int i=0; i<m; i++)
{
if(s[i] == 'S')
{
++r;
}
else if(s[i] == 'N')
{
--r;
}
else if(s[i] == 'W')
{
--c;
}
else if(s[i] == 'E')
{
++c;
}
if(!fr[r][c])
{
lr[r].push_back(c);
lc[c].push_back(r);
l.push_back({r,c});
}
fr[r][c] = true;
Max_r_riv = max(Max_r_riv, r);
}
for(int i=1; i<=R; i++)
{
if(!lr[i].size())
{
continue;
}
sort(lr[i].begin(),lr[i].end());
int st = 0, dr = 0;
st = lr[i].front();
for(int j=0; j<lr[i].size(); j++)
{
if(j==0 || lr[i][j] == lr[i][j - 1] + 1)
{
dr = lr[i][j];
}
else
{
sr[i].push_back({st,dr});
st = lr[i][j];
}
}
sr[i].push_back({st,dr});
}
for(int i=1; i<=C; i++)
{
if(!lc[i].size())
{
continue;
}
sort(lc[i].begin(),lc[i].end());
int st = 0, dr = 0;
st = lc[i].front();
for(int j=0; j<lc[i].size(); j++)
{
if(j==0 || lc[i][j] == lc[i][j - 1] + 1)
{
dr = lc[i][j];
}
else
{
sc[i].push_back({st,dr});
st = lc[i][j];
}
}
sc[i].push_back({st,dr});
}
for(auto it : l)
{
r = it.first;
c = it.second;
for(int p=0;p<8;p++)
{
int rr = r + dr[p];
int cc = c + dc[p];
if(!fr[rr][cc])
{
if(sv.find({rr,cc}) == sv.end())
{
r_nod[rr][cc] = (++nr_nod);
Min_r[nr_nod] = rr;
Max_r[nr_nod] = rr;
Min_c[nr_nod] = cc;
Max_c[nr_nod] = cc;
t[nr_nod] = nr_nod;
rang[nr_nod] = 1;
}
sv.insert({rr,cc});
}
}
}
for(auto it : l)
{
r = it.first;
c = it.second;
for(int p=0;p<8;p++)
{
int rr = r + dr[p];
int cc = c + dc[p];
if(!fr[rr][cc])
{
Add(rr,cc);
}
}
}
for(auto it=sv.begin();it!=sv.end();it++)
{
r = it->first;
c = it->second;
int nod = r_nod[r][c];
nod = rep(nod);
if(sel[nod])
{
continue;
}
if(Max_r[nod] > Max_r_riv)
{
continue;
}
l_nod.push_back(nod);
sel[nod] = true;
}
}
int inter(int a, int b, int c, int d)
{
if(a > c)
{
swap(a,c);
swap(b,d);
}
if(b < c)
{
return 0;
}
return 1;
}
int solve(vector<pair<int,int>> s, int a, int b)
{
if(s.empty())
{
return 0;
}
int poz_a = -1, poz_b = s.size();
int st = 0;
int dr = s.size() - 1;
while(st<=dr)
{
int mij = (st + dr) >> 1;
if(s[mij].first <= a)
{
poz_a = mij;
st = mij + 1;
}
else
{
dr = mij - 1;
}
}
st = 0;
dr = s.size() - 1;
while(st<=dr)
{
int mij = (st + dr) >> 1;
if(s[mij].second >= b)
{
poz_b = mij;
dr = mij - 1;
}
else
{
st = mij + 1;
}
}
if(poz_a == poz_b)
{
return 1;
}
int rez = poz_b - 1 - poz_a;
if(poz_a != -1)
{
rez += inter(s[poz_a].first, s[poz_a].second, a, b);
}
if(poz_b != s.size())
{
rez += inter(s[poz_b].first, s[poz_b].second, a, b);
}
return rez;
}
int colour(int ar, int ac, int br, int bc)
{
int rez = 0;
rez += solve(sr[ar], ac, bc);
rez += solve(sr[br], ac, bc);
rez += solve(sc[ac], ar, br);
rez += solve(sc[bc], ar, br);
if(rez == 0)
{
++rez;
}
rez -= fr[ar][ac];
rez -= fr[ar][bc];
rez -= fr[br][ac];
rez -= fr[br][bc];
for(auto it : l_nod)
{
if(Min_r[it] > ar && Max_r[it] < br && Min_c[it] > ac && Max_c[it] < bc)
{
++rez;
}
}
return rez;
}
Compilation message
rainbow.cpp: In function 'void init(int, int, int, int, int, char*)':
rainbow.cpp:117:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
117 | for(int j=0; j<lr[i].size(); j++)
| ~^~~~~~~~~~~~~
rainbow.cpp:140:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
140 | for(int j=0; j<lc[i].size(); j++)
| ~^~~~~~~~~~~~~
rainbow.cpp: In function 'int solve(std::vector<std::pair<int, int> >, int, int)':
rainbow.cpp:271:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
271 | if(poz_b != s.size())
| ~~~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
52056 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
52056 KB |
Output is correct |
| 2 |
Correct |
9 ms |
51804 KB |
Output is correct |
| 3 |
Incorrect |
564 ms |
91876 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
51804 KB |
Output is correct |
| 2 |
Correct |
741 ms |
108788 KB |
Output is correct |
| 3 |
Correct |
224 ms |
108500 KB |
Output is correct |
| 4 |
Correct |
207 ms |
103364 KB |
Output is correct |
| 5 |
Correct |
246 ms |
94972 KB |
Output is correct |
| 6 |
Correct |
48 ms |
55800 KB |
Output is correct |
| 7 |
Correct |
85 ms |
59084 KB |
Output is correct |
| 8 |
Incorrect |
482 ms |
94772 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
52056 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
52056 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
