.

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;
}

全部评论

相关推荐

03-03 23:12
已编辑
北京邮电大学 Java
书海为家:我来给一点点小建议,因为毕竟还在学校不像工作几年的老鸟有丰富的项目经验,面试官在面试在校生的时候更关注咱们同学的做事逻辑和思路,所以最好在简历中描述下自己做过项目的完整过程,比如需求怎么来的,你对需求的解读,你想到的解决办法,遇到困难如何找人求助,最终项目做成了什么程度,你从中收获了哪些技能,你有什么感悟。
你的简历改到第几版了
点赞 评论 收藏
分享
01-30 09:45
燕山大学 Java
喵_coding:这种直接跑就完事了 哪有毕业了才签合同 任何offer和三方都没有的
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务