10分求调
查看原帖
10分求调
1120842
XYM20230422楼主2024/10/15 13:59
#include<bits/stdc++.h>
using namespace std;
vector<int>a1[200005];
vector<int>a2[200005];
vector<int>a3[200005];
struct h{
	int w;
	long long v;
};
bool cmp(h d,h i){
	return d.v>i.v;
}
h g1[2000050],s1[2000050],b1[2000050];
int dpa[2000050],dpb[2000050],dpc[2000050],n,p[2000050];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>g1[i].v>>s1[i].v>>b1[i].v;
		g1[i].w=i;
		s1[i].w=i;
		b1[i].w=i;
	}
	sort(g1+1,g1+n+1,cmp);
	sort(s1+1,s1+n+1,cmp);
	sort(b1+1,b1+n+1,cmp);
	int x=1,y=1,z=1;
	memset(p,0x3f,sizeof(p));
	a1[1].push_back(g1[1].w);
	a2[1].push_back(s1[1].w);
	a3[1].push_back(b1[1].w);
	for(int i=2;i<=n;i++){
		if(g1[i].v==g1[i-1].v){
			a1[x].push_back(g1[i].w);
		}else{
			a1[++x].push_back(g1[i].w);
		}
		if(s1[i].v==s1[i-1].v){
			a2[y].push_back(s1[i].w);
		}else{
			a2[++y].push_back(s1[i].w);
		}
		if(b1[i].v==b1[i-1].v){
			a2[z].push_back(b1[i].w);
		}else{
			a2[++z].push_back(b1[i].w);
		}
	}
	dpa[1]=1;
	dpb[1]=1;
	dpc[1]=1;
	for(int i=2;i<=x;i++){
		dpa[i]=dpa[i-1]+a1[i-1].size();
	}
	for(int i=2;i<=y;i++){
		dpb[i]=dpb[i-1]+a2[i-1].size();
	}
	for(int i=2;i<=z;i++){
		dpc[i]=dpc[i-1]+a3[i-1].size();
	}
	for(int i=1;i<=x;i++){
		for(auto j:a1[i]){
			p[j]=min(p[j],dpa[i]);
		}
	}
	for(int i=1;i<=y;i++){
		for(auto j:a2[i]){
			p[j]=min(p[j],dpb[i]);
		}
	}
	for(int i=1;i<=z;i++){
		for(auto j:a3[i]){
			p[j]=min(p[j],dpc[i]);
		}
	}
	for(int i=1;i<=n;i++){
		cout<<p[i]<<endl;
	}
}
2024/10/15 13:59
加载中...