#include <bits/stdc++.h>
#define N 80005
#define M 250000
#define INF 2000000000000000005ll
using namespace std;
int dep[N];
int ans[N];
int par[N];
int pr[N];
set<int> col[N];
vector<int> de[N];
map<int,int> cmp;
map<int,int> rel;
multiset<pair<long long,pair<long long,long long>>> t[M*4];
struct Node{
int a,b,c,d,pos;
bool operator < (const Node other)const{
if(a == other.a){
return 1ll*(c-a)*(rel[d]-rel[b]) >= 1ll*(other.c-other.a)*(rel[other.d]-rel[other.b]);
}
return a < other.a;
}
};
void upd(int v,int tl,int tr,int l,int r,long long val1,long long val2,long long val3,int ok){
if(tr < l || r < tl){
return;
}
if(l <= tl && tr <= r){
if(ok){
assert(t[v].count({val1,{val2,val3}}));
t[v].erase(t[v].find({val1,{val2,val3}}));
}
else{
t[v].insert({val1,{val2,val3}});
}
return;
}
int tm = (tl+tr)/2;
upd(v*2,tl,tm,l,r,val1,val2,val3,ok);
upd(v*2+1,tm+1,tr,l,r,val1,val2,val3,ok);
}
pair<long long,pair<long long,long long>> get(int v,int l,int r,int pos){
int m = (l+r)/2;
if(l == r){
if(t[v].empty()){
return make_pair(INF,make_pair(INF,INF));
}
return *t[v].begin();
}
if(pos<=m){
if(t[v].empty()){
return min(make_pair(INF,make_pair(INF,INF)),get(v*2,l,m,pos));
}
return min(*t[v].begin(),get(v*2,l,m,pos));
}
else{
if(t[v].empty()){
return min(make_pair(INF,make_pair(INF,INF)),get(v*2+1,m+1,r,pos));
}
return min(*t[v].begin(),get(v*2+1,m+1,r,pos));
}
}
void go_par(int v){
ans[v] = col[pr[v]].size();
if(par[v] == -1){
return;
}
if(col[pr[v]].size() > col[pr[par[v]]].size()){
for(auto u:col[pr[par[v]]]){
col[pr[v]].insert(u);
}
pr[par[v]] = pr[v];
}
else{
for(auto u:col[pr[v]]){
col[pr[par[v]]].insert(u);
}
}
}
void solve(){
int n,m;
cin >> n >> m;
vector<Node> v;
vector<int> compress;
for(int i = 0;i<n;i++){
int a,b,c,d;
cin >> a >> b >> c >> d;
v.push_back({a,b,c,d,i});
compress.push_back(b);
compress.push_back(d);
}
vector<pair<int,pair<int,int>>> v2;
for(int i=0;i<m;i++){
int a,b,c;
cin >> a >> b >> c;
v2.push_back({a,{b,c}});
compress.push_back(b);
}
sort(compress.begin(),compress.end());
int cm = 1;
for(int i = 0;i<compress.size();i++){
if(rel[cm-1] != compress[i]){
cmp[compress[i]] = cm;
rel[cm] = compress[i];
cm++;
}
}
assert(M > cm);
for(auto &u:v){
u.b = cmp[u.b];
u.d = cmp[u.d];
}
for(auto &u:v2){
u.second.first = cmp[u.second.first];
}
sort(v2.begin(),v2.end());
sort(v.begin(),v.end());
set<pair<int,Node>> s;
for(auto u:v){
//cout << u.a << " " << u.b << " " << u.c << " " << u.d<< endl;
while(s.size() && s.begin()->first < u.a){
auto k = s.begin()->second;
s.erase(s.begin());
upd(1,1,M,k.b,k.d,1ll*(k.c-k.a)*(rel[k.d]-rel[k.b]) ,dep[k.pos],k.pos,1);
}
auto k = get(1,1,M,u.b);
if(k.first == INF){
par[u.pos] = -1;
}
else{
dep[u.pos] = dep[k.second.second] - 1;
par[u.pos] = k.second.second;
}
s.insert({u.c,u});
upd(1,1,M,u.b,u.d,1ll*(u.c-u.a)*(rel[u.d]-rel[u.b]) ,dep[u.pos],u.pos,0);
}
for(int i=0;i<M*4;i++){
t[i].clear();
}
s.clear();
int cnt = 0;
for(auto u:v2){
while(cnt != n && v[cnt].a <= u.first){
auto k = v[cnt];
upd(1,1,M,k.b,k.d,1ll*(k.c-k.a)*(rel[k.d]-rel[k.b]) ,dep[k.pos],k.pos,0);
s.insert({k.c,k});
cnt++;
}
while(s.size() && s.begin()->first < u.first){
auto k = s.begin()->second;
s.erase(s.begin());
upd(1,1,M,k.b,k.d,1ll*(k.c-k.a)*(rel[k.d]-rel[k.b]) ,dep[k.pos],k.pos,1);
}
auto k = get(1,1,M,u.second.first);
if(k.first == INF){
continue;
}
else{
col[k.second.second].insert(u.second.second);
}
}
for(int i=0;i<n;i++){
dep[i] = -1*dep[i];
pr[i] = i;
de[dep[i]].push_back(i);
}
for(int i=n;i>=0;i--){
for(auto u:de[i]){
go_par(u);
}
}
for(int i=0;i<n;i++){
cout << ans[i] << endl;
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
#ifdef Local
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
int t=1;
//cin>>t;
while(t--){
solve();
}
#ifdef Local
cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
#endif
}
Compilation message
plahte.cpp: In function 'void solve()':
plahte.cpp:101:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
101 | for(int i = 0;i<compress.size();i++){
| ~^~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
443 ms |
65120 KB |
Output is correct |
| 2 |
Correct |
428 ms |
65100 KB |
Output is correct |
| 3 |
Correct |
47 ms |
52972 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
600 ms |
79800 KB |
Output is correct |
| 2 |
Correct |
594 ms |
71040 KB |
Output is correct |
| 3 |
Correct |
44 ms |
53004 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1071 ms |
107716 KB |
Output is correct |
| 2 |
Correct |
982 ms |
77056 KB |
Output is correct |
| 3 |
Correct |
42 ms |
52972 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1792 ms |
142580 KB |
Output is correct |
| 2 |
Correct |
1654 ms |
87164 KB |
Output is correct |
| 3 |
Correct |
44 ms |
52972 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1683 ms |
127260 KB |
Output is correct |
| 2 |
Correct |
1609 ms |
85240 KB |
Output is correct |
| 3 |
Correct |
42 ms |
52972 KB |
Output is correct |
