# Jam's problem again

Time Limit: 5000/2500 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 640    Accepted Submission(s): 210

Problem Description

Jam like to solve the problem which on the 3D-axis,given  points  If two point such as  and , the bigger one level add  Ask for the each level of the point.

Input

The first line is  means  Case For each case The first line is  means the number of Point and next there are  line, each line has

Output

Output with N line,each line has one number means the lever of point

Sample Input

```1
4
10 4 7
10 6 6
8 2 5
7 3 10```

Sample Output

```1
1
0
0

#include <string.h>
#include <algorithm>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>

using namespace std;
typedef long long int LL;
const int maxn=1e5;
struct Node
{
int x,y,z;
int id;
int num;
}a[maxn+5];
int n;
int rt[maxn+5];
int ls[maxn*50];
int rs[maxn*50];
int sum[maxn*50];
int p;
int ans1,ans2;
int newnode()
{
ls[p]=rs[p]=sum[p]=0;
return p++;
}
int lowbit(int x)
{
return x&(-x);
}
int cmp(Node a,Node b)
{
if(a.x!=b.x)
return a.x<b.x;
else
{
if(a.y!=b.y)
return a.y<b.y;
else
return a.z<b.z;
}
}
int cmp2(Node a,Node b)
{
return a.id<b.id;
}
void insert(int &node,int l,int r,int tag)
{
if(!node)
node=newnode();
if(l==r)
{
sum[node]++;
return;
}
sum[node]++;
int mid=(l+r)>>1;
if(tag<=mid)
insert(ls[node],l,mid,tag);
else
insert(rs[node],mid+1,r,tag);
}
int query(int &node,int l,int r,int tag)
{
if(!node) return 0;
if(r<=tag)
{
return sum[node];
}
int mid=(l+r)>>1;
if(tag<=mid) return query(ls[node],l,mid,tag);
else return sum[ls[node]]+query(rs[node],mid+1,r,tag);
}
int find(int y,int z)
{
int res=0;
for(int i=y;i>=1;i-=lowbit(i))
{
res+=query(rt[i],1,ans2,z);
}
return res;
}
void update(int y,int z)
{
for(int i=y;i<=maxn;i+=lowbit(i))
{
insert(rt[i],1,ans2,z);
}
}
void init(int y,int z)
{
memset(rt,0,sizeof(rt));
for(int i=1;i<=y;i++)
{
rt[i]=i;
ls[i]=rs[i]=sum[i]=0;
}
p=y+1;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
ans1=0;  ans2=0;
for(int i=1;i<=n;i++)
{
scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
ans1=max(ans1,a[i].y);
ans2=max(ans2,a[i].z);
a[i].id=i;a[i].num=0;
}
sort(a+1,a+n+1,cmp);
for(int i=n-1;i>=1;i--)
{
if(a[i].x==a[i+1].x&&a[i].y==a[i+1].y&&a[i].z==a[i+1].z)
a[i].num=a[i+1].num+1;
}

init(ans1,ans2);
for(int i=1;i<=n;i++)
{
a[i].num+=find(a[i].y,a[i].z);
update(a[i].y,a[i].z);

}
sort(a+1,a+n+1,cmp2);
for(int i=1;i<=n;i++)
{
printf("%d\n",a[i].num);
}
}
return 0;
}

#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <stdio.h>
#include <string.h>

using namespace std;
typedef long long int LL;
const int maxn=1e5;
int n;
struct Node
{
int x,y,z;
int id;
int num;
}a[maxn+5],b[maxn+5];
int c[maxn+5];
int cmp(Node a,Node b)
{
if(a.x==b.x&&a.y==b.y)
return a.z<b.z;
if(a.x==b.x)
return a.y<b.y;
return a.x<=b.x;
}
int cmp2(Node a,Node b)
{
return a.id<b.id;
}
int lowbit(int x)
{
return x&(-x);
}
void insert(int x,int y)
{
for(int i=x;i<=maxn;i+=lowbit(i))
c[i]+=y;
}
int sum(int x)
{
int s=0;
for(int i=x;i>=1;i-=lowbit(i))
s+=c[i];
return s;
}
void fun(int l,int r)
{
if(l==r) return;
int mid=(l+r)>>1;
int j=l;
int k=mid+1;
fun(l,mid);
fun(mid+1,r);
for(int i=l;i<=r;i++)
{
if((a[j].y<=a[k].y||k>r)&&j<=mid)
{
b[i]=a[j++];
insert(b[i].z,1);
}
else
{
b[i]=a[k++];
b[i].num+=sum(b[i].z);
}
}
for(int i=l;i<=r;i++)
{
if(i<=mid)
insert(a[i].z,-1);
a[i]=b[i];
}
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
memset(c,0,sizeof(c));
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
a[i].id=i;a[i].num=0;
}
sort(a+1,a+n+1,cmp);
for(int i=n-1;i>=1;i--)
{
if(a[i].x==a[i+1].x&&a[i].y==a[i+1].y&&a[i].z==a[i+1].z)
a[i].num=a[i+1].num+1;
}
fun(1,n);
sort(a+1,a+n+1,cmp2);
for(int i=1;i<=n;i++)
{
printf("%d\n",a[i].num);
}
}
return 0;
}

#include <string.h>
#include <algorithm>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>

using namespace std;
typedef long long int LL;
const int maxn=1e5;
struct Node
{
int x,y,z;
int id,num;
int tag;

}a[maxn+5],b[maxn+5],c[maxn+5];
int ans[maxn+5];
int n;

int cmp(Node a,Node b)
{
if(a.x==b.x&&a.y==b.y)
return a.z<b.z;
if(a.x==b.x)
return a.y<b.y;
return a.x<b.x;
}
int cmp2(Node a,Node b)
{
return a.id<b.id;
}
void fun2(int l,int r)
{
if(l==r) return;
int mid=(l+r)>>1;
fun2(l,mid);
fun2(mid+1,r);
int j=l;
int k=mid+1;
int res=0;
for(int i=l;i<=r;i++)
{
if((b[j].z<=b[k].z||k>r)&&j<=mid)
{
c[i]=b[j++];
if(!c[i].tag)
res++;
}
else
{
c[i]=b[k++];
if(c[i].tag)
c[i].num+=res,ans[c[i].id]+=res;
}
}
for(int i=l;i<=r;i++)
b[i]=c[i];
}
void fun1(int l,int r)
{

if(l==r)
return;
int mid=(l+r)>>1;
fun1(l,mid);
fun1(mid+1,r);
int j=l;
int k=mid+1;
for(int i=l;i<=r;i++)
{
if((a[j].y<=a[k].y||k>r)&&j<=mid)
{
b[i]=a[j++];
b[i].tag=0;
}
else
{
b[i]=a[k++];
b[i].tag=1;
}
}
for(int i=l;i<=r;i++)
a[i]=b[i];

fun2(l,r);

}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
a[i].num=0;
a[i].tag=0;
a[i].id=i;

}
memset(ans,0,sizeof(ans));

sort(a+1,a+n+1,cmp);
for(int i=n-1;i>=1;i--)
if(a[i].x==a[i+1].x&&a[i].y==a[i+1].y&&a[i].z==a[i+1].z)
a[i].num=a[i+1].num+1,ans[a[i].id]=ans[a[i+1].id]+1;

fun1(1,n);
sort(a+1,a+n+1,cmp2);
for(int i=1;i<=n;i++)
printf("%d\n",ans[i]);
}
return 0;
}```

0 条评论

• ### LeetCode 1632. Rank Transform of a Matrix

思路是贪心，将所有的元素从小到大排序。并且维护两个数组，一个数组代表每一行的当前已经填上的最大的rank，比如nrank[0]=2 表示第0行，目前已经填到了r...

• ### 第7章 套接字选项

这一章是一个无比巨大的巨坑！！！ 套接字选项相关函数： #include <sys/socket.h> int getsockopt(int sock, i...

• ### 指针详解（一）

C语言可谓是因为指针而拥有了其他的语言所不拥有的作用，但是却又因为指针导致它对于初学者而言是一个很难克服的难题。接下来我们直切主体——指针。

• ### 一套帮助你理解C语言的测试题（转）

原文链接：http://www.nowamagic.net/librarys/veda/detail/775

• ### C语言实现计算器（指针+函数）

输入两个整数a和b，及+，-，*，/中的任意一字符。根据输入字符对整数a和b做相应的算术运算，如输入+，程序就给出a与b之和，输入-，就给出a和b之差，输入*，...

• ### 一遍记住Java常用的八种排序算法

(如果每次比较都交换，那么就是交换排序；如果每次比较完一个循环再交换，就是简单选择排序。)

• ### 学生时代所学的一些 C 语言知识点回顾（1）

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

• ### ICPC Asia Shenyang 2019 Dudu's maze

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。