#include<iostream>
#include<algorithm>
#include<stack>
#include<set>
#include<vector>
#define DIM 80005
using namespace std;
int n, m, i, nr, x, y, x2, y2;
int w[3 * DIM], t[DIM], ff[DIM], sol[DIM];
stack<int> aint[700000];
set<int> s[DIM];
struct str{
int t, x, y, y2, col, ind;
};
str v[3 * DIM];
vector<int> vec[DIM];
int cmp(str a, str b){
if(a.x == b.x){
return a.t < b.t;
}
return a.x < b.x;
}
int cautbin(int x){
int st = 1, dr = nr, mid;
while(st <= dr){
mid = (st + dr) / 2;
if(w[mid] == x){
return mid;
}
if(w[mid] < x){
st = mid + 1;
}
else{
dr = mid - 1;
}
}
}
void update(int nod, int st, int dr, int p, int u, int ind){
if(p <= st && dr <= u){
aint[nod].push(ind);
}
else{
int mid = (st + dr) / 2;
if(p <= mid){
update(2 * nod, st, mid, p, u, ind);
}
if(u > mid){
update(2 * nod + 1, mid + 1, dr, p, u, ind);
}
}
}
void update2(int nod, int st, int dr, int p, int u){
if(p <= st && dr <= u){
aint[nod].pop();
}
else{
int mid = (st + dr) / 2;
if(p <= mid){
update2(2 * nod, st, mid, p, u);
}
if(u > mid){
update2(2 * nod + 1, mid + 1, dr, p, u);
}
}
}
int query(int nod, int st, int dr, int p){
int x = 0;
if( !aint[nod].empty() ){
x = aint[nod].top();
}
if(st != dr){
int mid = (st + dr) / 2;
if(p <= mid){
x = max(x, query(2 * nod, st, mid, p) );
}
else{
x = max(x, query(2 * nod + 1, mid + 1, dr, p) );
}
}
return x;
}
void dfs(int nod){
if(vec[nod].size() == 0){
ff[nod] = nod;
sol[nod] = s[nod].size();
return;
}
for(int i = 0; i < vec[nod].size(); i++){
dfs(vec[nod][i]);
}
ff[nod] = ff[ vec[nod][0] ];
for(int i = 1; i < vec[nod].size(); i++){
int vecin = vec[nod][i];
if(s[ ff[nod] ].size() < s[ ff[vecin] ].size() ){
ff[nod] = ff[vecin];
}
}
set<int>::iterator it;
for(int i = 0; i < vec[nod].size(); i++){
int vecin = vec[nod][i];
if(ff[vecin] == ff[nod]){
continue;
}
for(it = s[ ff[vecin] ].begin(); it != s[ ff[vecin] ].end(); it++){
s[ ff[nod] ].insert(*it);
}
}
for(it = s[nod].begin(); it != s[nod].end(); it++){
s[ ff[nod] ].insert(*it);
}
sol[nod] = s[ ff[nod] ].size();
}
int main(){
cin>> n >> m;
for(i = 1; i <= n; i++){
cin>> x >> y >> x2 >> y2;
v[2 * i - 1].ind = v[2 * i].ind = i;
v[2 * i - 1].y = v[2 * i].y = y;
v[2 * i - 1].y2 = v[2 * i].y2 = y2;
v[2 * i - 1].x = x;
v[2 * i].x = x2;
v[2 * i - 1].t = 1;
v[2 * i].t = 3;
w[2 * i - 1] = y;
w[2 * i] = y2;
}
for(i = 2 * n + 1; i <= 2 * n + m; i++){
cin>> v[i].x >> v[i].y >> v[i].col;
v[i].t = 2;
w[i] = v[i].y;
}
m += 2 * n;
sort(w + 1, w + m + 1);
nr = 1;
for(i = 2; i <= m; i++){
if(w[i] != w[nr]){
w[++nr] = w[i];
}
}
for(i = 1; i <= m; i++){
v[i].y = cautbin(v[i].y);
if(v[i].y2 != 0){
v[i].y2 = cautbin(v[i].y2);
}
}
sort(v + 1, v + m + 1, cmp);
for(i = 1; i <= m; i++){
if(v[i].t == 1){
x = query(1, 1, nr, v[i].y);
t[ v[i].ind ] = v[x].ind;
update(1, 1, nr, v[i].y, v[i].y2, i);
continue;
}
if(v[i].t == 2){
x = query(1, 1, nr, v[i].y);
if(x != 0){
s[ v[x].ind ].insert(v[i].col);
}
continue;
}
update2(1, 1, nr, v[i].y, v[i].y2);
}
for(i = 1; i <= n; i++){
vec[ t[i] ].push_back(i);
}
for(i = 1; i <= n; i++){
if(t[i] == 0){
dfs(i);
}
}
for(i = 1; i <= n; i++){
cout<< sol[i] <<"\n";
}
}
Compilation message
plahte.cpp: In function 'void dfs(int)':
plahte.cpp:88:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < vec[nod].size(); i++){
~~^~~~~~~~~~~~~~~~~
plahte.cpp:92:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 1; i < vec[nod].size(); i++){
~~^~~~~~~~~~~~~~~~~
plahte.cpp:99:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < vec[nod].size(); i++){
~~^~~~~~~~~~~~~~~~~
plahte.cpp: In function 'int cautbin(int)':
plahte.cpp:37:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
696 ms |
483952 KB |
Output is correct |
| 2 |
Correct |
698 ms |
484532 KB |
Output is correct |
| 3 |
Correct |
487 ms |
477360 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
748 ms |
485120 KB |
Output is correct |
| 2 |
Correct |
733 ms |
484728 KB |
Output is correct |
| 3 |
Correct |
479 ms |
477304 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
923 ms |
491392 KB |
Output is correct |
| 2 |
Correct |
915 ms |
489256 KB |
Output is correct |
| 3 |
Correct |
483 ms |
477292 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1204 ms |
499632 KB |
Output is correct |
| 2 |
Correct |
1215 ms |
497660 KB |
Output is correct |
| 3 |
Correct |
486 ms |
477176 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1197 ms |
498448 KB |
Output is correct |
| 2 |
Correct |
1205 ms |
496916 KB |
Output is correct |
| 3 |
Correct |
485 ms |
477300 KB |
Output is correct |
