#include <cstdio>
#include <set>
#include <vector>
#include <algorithm>
#define INF 2000000000
#define DIMN 80010
using namespace std;
int dist , idx , level_sol;
int norm[2*DIMN],tata[DIMN] , sol[DIMN];
vector <int> v[DIMN];
set <int> cul[DIMN];
struct eveniment{
int y,tip,idx;
} e[2*DIMN];
struct sheet{
int x1,x2,y1,y2;
} s[DIMN];
struct punct{
int x,y,c;
}pct[DIMN];
struct segment_tree{
int ok , level , idx;
}aint[DIMN * 4];
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;
aint[nod].ok = 1;
if (l<=st && dr<=r){
aint[nod].ok = 1;
aint[nod].idx = val;
aint[nod].level = 1 + level_sol;
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<=st && dr<=r){
aint[nod].ok = 0;
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 (aint[nod].ok == 0)
return;
if (aint[nod].ok && 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[vecin]].size() > sz_max){
sz_max = cul[tata[vecin]].size();
heavy = vecin;
}
}
if (!sz_max){ /// nu ai fii de la care sa iei informatii
sol[nod] = cul[tata[nod]].size();
return;
}
if (cul[nod].size() > sz_max){
sz_max = cul[nod].size();
heavy = nod;
}
tata[nod] = tata[heavy]; /// il alipesti la padurea aia
/// merge si erase
if (heavy!=nod){
cul[tata[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[nod]].insert(cul[tata[vecin]].begin() , cul[tata[vecin]].end());
cul[tata[vecin]].clear();
}
}
sol[nod] = cul[tata[nod]].size();
}
int main()
{
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[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);
}
add(1,1,dist,y1,y2,e[i].idx);
}
else if (e[i].tip == 1){ /// punct
level_sol = 0;
qry(1,1,dist,y,y);
cul[idx].insert(pct[e[i].idx].c);
}
else { /// se termina dreptunghi
del(1,1,dist,y1,y2);
}
}
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:101:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0;i<v[nod].size();i++){
~^~~~~~~~~~~~~~
plahte.cpp:104:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (cul[tata[vecin]].size() > sz_max){
~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~
plahte.cpp:114:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (cul[nod].size() > sz_max){
~~~~~~~~~~~~~~~~^~~~~~~~
plahte.cpp:129: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:144: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:165: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:188: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 |
Incorrect |
116 ms |
14328 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
150 ms |
15884 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
134 ms |
27768 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
61 ms |
13004 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
60 ms |
13048 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
