.

Contest

http://www.nowcoder.com/questionTerminal/1e9d3c4b48b34dafb87b5ee883ffedc4

include<stdio.h>

include

using namespace std;
#define LL long long
typedef struct Res
{
LL x, y, z;
bool operator < (const Res &b) const
{
if(x<b.x || x==b.x && y<b.y || x==b.x && y==b.y && z<b.z)
return 1;
return 0;
}
}Res;
LL ans, n, tre[200005];
Res s[200005], L[200005], R[200005];
void Update(LL x, LL val)
{
while(x<=n)
{
tre[x] += val;
x += x&-x;
}
}
LL Query(LL x)
{
LL ans = 0;
while(x)
{
ans += tre[x];
x -= x&-x;
}
return ans;
}
void Cdq(LL l, LL r)
{
LL i, p, q, m;
if(l==r)
return;
m = (l+r)/2;
for(i=l;i<=r;i++)
{
if(s[i].z<=m)
Update(s[i].y, 1);
else
ans += Query(s[i].y);
}
for(i=l;i<=r;i++)
{
if(s[i].z<=m)
Update(s[i].y, -1);
}
p = q = 0;
for(i=l;i<=r;i++)
{
if(s[i].z<=m)
L[++p] = s[i];
else
R[++q] = s[i];
}
for(i=l;i<=m;i++)
s[i] = L[i-(l-1)];
for(i=m+1;i<=r;i++)
s[i] = R[i-m];
Cdq(l, m);
Cdq(m+1, r);
}
int main(void)
{
LL i;
scanf("%lld", &n);
for(i=1;i<=n;i++)
scanf("%lld%lld%lld", &s[i].x, &s[i].y, &s[i].z);
sort(s+1, s+n+1);
Cdq(1, n);
printf("%lld\n", n*(n-1)/2-ans);
return 0;
}

全部评论

相关推荐

10-25 12:05
已编辑
湖南科技大学 Java
若梦难了:我有你这简历,已经大厂乱杀了
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务