QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#753957#9557. Temperanceucup-team5319#RE 0ms0kbC++141.8kb2024-11-16 13:56:502024-11-16 13:56:51

Judging History

你现在查看的是最新测评结果

  • [2024-11-16 13:56:51]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-11-16 13:56:50]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+9;
struct Point{
	int x,y,z;
}a[N];
int lsh[N];
int n;
vector<int> vx[N],vy[N],vz[N];
vector<int> bucx[N],bucy[N],bucz[N];
bool vis[N];
int ans[N];
void work()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
	
	for(int i=1;i<=n;i++) lsh[i]=a[i].x;
	int lmx=unique(lsh+1,lsh+n+1)-lsh-1;
	for(int i=1;i<=n;i++) a[i].x=lower_bound(lsh+1,lsh+lmx+1,a[i].x)-lsh;
	for(int i=1;i<=n;i++) assert(a[i].x<=lmx);
	for(int i=1;i<=lmx;i++) vx[i].clear();
	
	for(int i=1;i<=n;i++) lsh[i]=a[i].y;
	int lmy=unique(lsh+1,lsh+n+1)-lsh-1;
	for(int i=1;i<=n;i++) a[i].y=lower_bound(lsh+1,lsh+lmy+1,a[i].y)-lsh;
	for(int i=1;i<=n;i++) assert(a[i].y<=lmy);
	for(int i=1;i<=lmy;i++) vy[i].clear();
	
	for(int i=1;i<=n;i++) lsh[i]=a[i].z;
	int lmz=unique(lsh+1,lsh+n+1)-lsh-1;
	for(int i=1;i<=n;i++) a[i].z=lower_bound(lsh+1,lsh+lmz+1,a[i].z)-lsh;
	for(int i=1;i<=n;i++) assert(a[i].z<=lmz);
	for(int i=1;i<=lmz;i++) vz[i].clear();
	
	for(int i=0;i<=n;i++) bucx[i].clear(),bucy[i].clear(),bucz[i].clear();
	
	for(int i=1;i<=n;i++)
	{
		vx[a[i].x].push_back(i);
		vy[a[i].y].push_back(i);
		vz[a[i].z].push_back(i);
		vis[i]=0;
	}
	for(int i=1;i<=lmx;i++) bucx[vx[i].size()].push_back(i);
	for(int i=1;i<=lmy;i++) bucy[vy[i].size()].push_back(i);
	for(int i=1;i<=lmz;i++) bucz[vz[i].size()].push_back(i);
	
	int cnt=0;
	for(int i=n;i>=1;i--)
	{
		for(int id:bucx[i])
			for(int x:vx[id])
				if(!vis[x]) vis[x]=1,cnt++;
		for(int id:bucy[i])
			for(int y:vy[id])
				if(!vis[y]) vis[y]=1,cnt++;
		for(int id:bucz[i])
			for(int z:vz[id])
				if(!vis[z]) vis[z]=1,cnt++;
		ans[i]=n-cnt;
	}
	for(int i=1;i<=n;i++) printf("%d ",ans[i]);
	puts("");
}
signed main()
{
	int T;
	scanf("%d",&T);
	while(T--) work();
}

详细

Test #1:

score: 0
Runtime Error

input:

2
5
1 1 1
1 1 2
1 1 3
2 3 5
2 2 4
3
1 1 1
2 2 2
3 3 3

output:


result: