#include <cstdio>
#include <set>
#include <vector>
#include <algorithm>
#define INF 2000000000
#define DIMN 80010
using namespace std;
int dist , idx , level_sol;
int norm[3*DIMN],tata_dsu[DIMN] , sol[DIMN],tata[DIMN];
vector <int> v[DIMN];
set <int> cul[DIMN];
struct eveniment{
int y,tip,idx;
} e[3*DIMN];
struct sheet{
int x1,x2,y1,y2;
} s[DIMN];
struct punct{
int x,y,c;
}pct[DIMN];
struct segment_tree{
int level , idx , apart;
}aint[DIMN * 12];
int cmp (eveniment a , eveniment b){
if (a.y!=b.y)
return a.y < b.y;
else if (a.tip != b.tip)
return a.tip < b.tip;
return a.idx < b.idx;
}
int findd(int x){
int st,dr,mid;
st = 1;
dr = dist;
while (st<=dr){
mid = (st + dr)/2;
if (norm[mid] == x)
return mid;
else if (norm[mid] < x)
st = mid + 1;
else dr = mid - 1;
}
return -1;
}
void add (int nod,int st,int dr,int l,int r,int val){
int mid;
if (l<=st && dr<=r){
//if (st == 5 && dr == 6)
// printf ("%d ",val);
aint[nod].idx = val;
aint[nod].level = 1 + level_sol;
aint[nod].apart++;
return;
}
mid = (st + dr)/2;
if (l<=mid)
add(2*nod,st,mid,l,r,val);
if (mid+1<=r)
add(2*nod+1,mid+1,dr,l,r,val);
}
void del (int nod,int st,int dr,int l,int r){
int mid;
//if ( l == 4 && r == 7)
// printf ("%d %d\n",st,dr);
if (l<=st && dr<=r){
if (aint[nod].apart > 1){
aint[nod].idx = tata[aint[nod].idx];
aint[nod].level--;
}
else {
aint[nod].idx = aint[nod].level = 0;
}
aint[nod].apart--;
return;
}
mid = (st + dr)/2;
if (l<=mid)
del(2*nod,st,mid,l,r);
if (mid+1<=r)
del(2*nod+1,mid+1,dr,l,r);
}
void qry (int nod,int st,int dr,int l,int r){
int mid = (st + dr)/2;
//if ( l == r && l == 5)
// printf ("%d %d %d %d %d\n",nod,st,dr,aint[nod].idx,aint[nod].level);
if (aint[nod].level > level_sol){
level_sol = aint[nod].level;
idx = aint[nod].idx;
}
if (l<=st && dr<=r){
return;
}
if (l<=mid)
qry(2*nod,st,mid,l,r);
if (mid+1<=r)
qry(2*nod+1,mid+1,dr,l,r);
}
void dfs (int nod){
int i,vecin,sz_max = 0 , heavy;
for (i=0;i<v[nod].size();i++){
vecin = v[nod][i];
dfs(vecin);
if (cul[tata_dsu[vecin]].size() > sz_max){
sz_max = cul[tata_dsu[vecin]].size();
heavy = vecin;
}
}
if (!sz_max){ /// nu ai fii de la care sa iei informatii
sol[nod] = cul[tata_dsu[nod]].size();
return;
}
if (cul[nod].size() > sz_max){
sz_max = cul[nod].size();
heavy = nod;
}
tata_dsu[nod] = tata_dsu[heavy]; /// il alipesti la padurea aia
/// merge si erase
if (heavy!=nod){
cul[tata_dsu[nod]].insert(cul[nod].begin() , cul[nod].end());
cul[nod].clear();
}
for (i=0;i<v[nod].size();i++){
vecin = v[nod][i];
if (vecin!=heavy){
cul[tata_dsu[nod]].insert(cul[tata_dsu[vecin]].begin() , cul[tata_dsu[vecin]].end());
cul[tata_dsu[vecin]].clear();
}
}
sol[nod] = cul[tata_dsu[nod]].size();
}
int main()
{
//FILE *fin = fopen ("a.in","r");
//FILE *fout = fopen ("a.out" , "w");
int n,m,elem,ev=0,i,x1,y1,x2,y2,x,y,c;
scanf ("%d%d",&n,&m);
elem = 0;
s[0].x1 = -INF;
s[0].x2 = INF;
s[0].y1 = -INF;
s[0].y2 = INF;
norm[++elem] = -INF;
norm[++elem] = INF;
ev++;
e[ev].y = -INF;
e[ev].tip = 0; /// incepe dreptunghi
e[ev].idx = 0;
ev++;
e[ev].y = INF;
e[ev].tip = 2; /// se termina dreptunghi
e[ev].idx = 0;
for (i=1;i<=n;i++){
scanf ("%d%d%d%d",&x1,&y1,&x2,&y2);
tata_dsu[i] = i; /// initializare pentru dsu
s[i].x1 = x1;
s[i].x2 = x2;
s[i].y1 = y1;
s[i].y2 = y2;
norm[++elem] = y1;
norm[++elem] = y2;
ev++;
e[ev].y = x1;
e[ev].tip = 0; /// incepe dreptunghi
e[ev].idx = i;
ev++;
e[ev].y = x2;
e[ev].tip = 2; /// se termina dreptunghi
e[ev].idx = i;
}
for (i=1;i<=m;i++){
scanf ("%d%d%d",&x,&y,&c);
norm[++elem] = y;
pct[i].x = x;
pct[i].y = y;
pct[i].c = c;
ev++;
e[ev].y = x;
e[ev].tip = 1; /// punct
e[ev].idx = i;
}
/// normalizare y
sort (norm + 1 , norm + elem + 1);
dist = 0;
for (i=1;i<=elem;i++){
if (dist == 0 || norm[i]!=norm[i-1])
norm[++dist] = norm[i];
}
/// dist = cati y distincti sunt , cb pe norm pt a afla echivalentul normalizat
sort (e + 1 , e + ev + 1 , cmp);
for (i=1 ; i<=ev ; i++){
if (e[i].tip!=1){
y1 = findd(s[e[i].idx].y1);
y2 = findd(s[e[i].idx].y2);
}
else y = findd(pct[e[i].idx].y);
if (e[i].tip == 0){ /// incepe dreptunghi
level_sol = 0;
if (e[i].idx){ /// nu e dreptunghiul fictiv
qry (1,1,dist,y1,y2);
v[idx].push_back(e[i].idx);
tata[e[i].idx] = idx;
}
add(1,1,dist,y1,y2,e[i].idx);
}
else if (e[i].tip == 1){ /// punct
//if (e[i].idx == 8)
// printf ("a");
level_sol = 0;
qry(1,1,dist,y,y);
cul[idx].insert(pct[e[i].idx].c);
//if (idx == 5)
//printf ("%d %d %d %d\n",pct[e[i].idx].x,pct[e[i].idx].y,pct[e[i].idx].c,e[i].idx);
}
else { /// se termina dreptunghi
//if (e[i].idx == 5)
// printf ("%d %d\n",y1,y2);
del(1,1,dist,y1,y2);
}
//if (aint[10].idx == 5)
//printf ("%d ",aint[10].idx);
}
dfs(0); /// dsu
for (i=1;i<=n;i++)
printf ("%d\n",sol[i]);
return 0;
}
Compilation message
plahte.cpp: In function 'void dfs(int)':
plahte.cpp:111:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0;i<v[nod].size();i++){
~^~~~~~~~~~~~~~
plahte.cpp:114:41: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (cul[tata_dsu[vecin]].size() > sz_max){
~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~
plahte.cpp:124:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (cul[nod].size() > sz_max){
~~~~~~~~~~~~~~~~^~~~~~~~
plahte.cpp:139:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0;i<v[nod].size();i++){
~^~~~~~~~~~~~~~
plahte.cpp: In function 'int main()':
plahte.cpp:156:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d%d",&n,&m);
~~~~~~^~~~~~~~~~~~~~
plahte.cpp:177:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d%d%d%d",&x1,&y1,&x2,&y2);
~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
plahte.cpp:200:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d%d%d",&x,&y,&c);
~~~~~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
119 ms |
13948 KB |
Output is correct |
| 2 |
Correct |
121 ms |
13560 KB |
Output is correct |
| 3 |
Correct |
7 ms |
6008 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
142 ms |
15592 KB |
Output is correct |
| 2 |
Correct |
140 ms |
15228 KB |
Output is correct |
| 3 |
Correct |
7 ms |
6012 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
250 ms |
23152 KB |
Output is correct |
| 2 |
Correct |
241 ms |
19064 KB |
Output is correct |
| 3 |
Correct |
7 ms |
6008 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
410 ms |
31632 KB |
Output is correct |
| 2 |
Correct |
418 ms |
28152 KB |
Output is correct |
| 3 |
Correct |
7 ms |
6008 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
408 ms |
29408 KB |
Output is correct |
| 2 |
Correct |
432 ms |
27756 KB |
Output is correct |
| 3 |
Correct |
7 ms |
6008 KB |
Output is correct |
