//#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>
#include <set>
#define DIM 80010
#define INF 2000000000
using namespace std;
//ifstream cin ("date.in");
//ofstream cout ("date.out");
struct point{
int x,y,c;
};
point points[DIM];
struct dreptunghi{
int x1,y1,x2,y2;
};
dreptunghi v[DIM];
struct event{
int tip; /// 1-inceput de dreptunghi, 2-bila, 3-se termina dreptunghi
int x; /// dreapta de baleiere
int idx; /// indexul dreptunghiului
};
vector <event> events;
vector <int> L[DIM];
deque <int> aint[4*DIM];
set <int> colors[DIM];
int t[DIM],sol[DIM],s[4*DIM],viz[DIM];
int n,m,i,j,X1,Y1,X2,Y2,x,y,c,maxim,sol_poz,maxi,el,k;
inline int cmp (event a, event b){
if (a.x == b.x)
return a.tip < b.tip; /// bila trebuie sa o pun pe contur
return a.x < b.x;
}
void update (int nod, int st, int dr, int x, int y, int val, int tip){
if (x <= st && dr <= y){
if (tip == 0) /// intra dreptunghi
aint[nod].push_back(val);
else aint[nod].pop_back();
return;
}
int mid = (st+dr)>>1;
if (x <= mid)
update (nod<<1,st,mid,x,y,val,tip);
if (y > mid)
update ((nod<<1)|1,mid+1,dr,x,y,val,tip);
}
void query (int nod, int st, int dr, int poz){
if (aint[nod].size()){
if (t[aint[nod].back()] > maxim){
maxim = t[aint[nod].back()];
sol_poz = aint[nod].back();
}}
if (st >= dr)
return;
int mid = (st+dr)>>1;
if (poz <= mid)
query (nod<<1,st,mid,poz);
else query ((nod<<1)|1,mid+1,dr,poz);
}
void dfs (int nod){
int aux = nod;
viz[nod] = 1;
for (int i=0;i<L[nod].size();i++){
int vecin = L[nod][i];
if (!viz[vecin]){
dfs (vecin);
/// acum trebuie sa dau merge la seturile culorilor
if (colors[aux].size() < colors[vecin].size())
swap (aux,vecin);
for (set<int>:: iterator it=colors[vecin].begin();it!=colors[vecin].end();it++)
colors[aux].insert(*it);
}}
sol[nod] = colors[aux].size();
swap (colors[aux],colors[nod]);
}
int cautare_binara (int v[], int n, int val){
int st = 1, dr = n;
while (st <= dr){
int mid = (st+dr)>>1;
if (v[mid] == val)
return mid;
if (v[mid] < val)
st = mid+1;
else dr = mid-1;
}
return -1;
}
int main (){
cin>>n>>m;
for (i=1;i<=n;i++){
cin>>X1>>Y1>>X2>>Y2;
events.push_back({1,X1,i});
events.push_back({3,X2,i});
v[i] = {X1,Y1,X2,Y2};
s[++el] = Y1, s[++el] = Y2;
}
/// adaug dreptunghiul mare care le cuprinde pe toate
v[0] = {-INF,-INF,INF,INF};
events.push_back({1,-INF,0});
events.push_back({3,INF,0});
s[++el] = -INF, s[++el] = INF;
for (i=1;i<=m;i++){
cin>>x>>y>>c;
events.push_back({2,x,i});
points[i] = {x,y,c};
s[++el] = y;
}
sort (events.begin(),events.end(),cmp);
/// elimin dublurile
sort (s+1,s+el+1);
k = 1;
for (i=2;i<=el;i++)
if (s[i] != s[i-1])
s[++k] = s[i];
maxi = k;
for (i=0;i<events.size();i++){
if (events[i].tip == 1){ /// inceput de dreptunghi
if (events[i].x != -INF){
/// trebuie sa aflu cel mai mic dreptunghi in care e inclus
/// ca sa construiesc graful
int poz = cautare_binara(s,k,v[events[i].idx].y1);
maxim = -1;
query (1,1,maxi,poz);
L[sol_poz].push_back(events[i].idx);
}
t[events[i].idx] = i+1; /// tin minte din ce dreapa de baleiere l am obtinut
/// acum il introduc in aint
int poz1 = cautare_binara(s,k,v[events[i].idx].y1);
int poz2 = cautare_binara(s,k,v[events[i].idx].y2);
update (1,1,maxi,poz1,poz2,events[i].idx,0);
continue;
}
if (events[i].tip == 3){
/// se termina dreptunghi, deci trebuie sa dau pop_back la stiva
int poz1 = cautare_binara(s,k,v[events[i].idx].y1);
int poz2 = cautare_binara(s,k,v[events[i].idx].y2);
update (1,1,maxi,poz1,poz2,events[i].idx,1);
continue;
}
/// bila
int poz = cautare_binara(s,k,points[events[i].idx].y);
maxim = -1;
query (1,1,maxi,poz);
/// trebuie sa inserez culoarea in setul dreptunghiului
colors[sol_poz].insert(points[events[i].idx].c);
}
dfs (0);
for (i=1;i<=n;i++)
cout<<sol[i]<<"\n";
return 0;
}
Compilation message
plahte.cpp: In function 'void dfs(int)':
plahte.cpp:66:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0;i<L[nod].size();i++){
~^~~~~~~~~~~~~~
plahte.cpp: In function 'int main()':
plahte.cpp:123:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0;i<events.size();i++){
~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
433 ms |
228136 KB |
Output is correct |
| 2 |
Correct |
444 ms |
228840 KB |
Output is correct |
| 3 |
Correct |
263 ms |
221432 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
505 ms |
229356 KB |
Output is correct |
| 2 |
Correct |
514 ms |
228944 KB |
Output is correct |
| 3 |
Correct |
272 ms |
221448 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
842 ms |
457536 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 |
Runtime error |
914 ms |
460368 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 |
Runtime error |
909 ms |
460436 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
