比赛 |
USACO银组重赛hhh |
评测结果 |
AAAAAAAAAA |
题目名称 |
Triangles(Silver) |
最终得分 |
100 |
用户昵称 |
梦那边的美好ET |
运行时间 |
0.234 s |
代码语言 |
C++ |
内存使用 |
19.00 MiB |
提交时间 |
2020-03-01 21:41:47 |
显示代码纯文本
#include<bits/stdc++.h>
#define maxn 300010
#define maxm 20010
#define LL long long
using namespace std;
const LL mod=(LL)1000000007,add=(LL)10000;
int n;
struct node{
LL x,y;
bool operator<(const node &a1)const{
if(x==a1.x)return y<a1.y;
return x<a1.x;
}
}a[maxn];
LL ans,su,sum,f[maxm],s[maxm],g[maxm],a1[maxm],a2[maxm];
void solve(int j){
ans=(ans+(a1[a[j].y]*a[j].x-a2[a[j].y]+mod)%mod*sum)%mod;
f[a[j].y]=((f[a[j].y]+(a[j].x-s[a[j].y])*g[a[j].y])%mod+mod)%mod;
s[a[j].y]=a[j].x;g[a[j].y]=(g[a[j].y]+sum)%mod;ans=(ans+f[a[j].y])%mod;
return;
}
int main(){
freopen("usaco_Feb_triangles.in","r",stdin);
freopen("usaco_Feb_triangles.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%lld%lld",&a[i].x,&a[i].y),
a[i].x+=add,a[i].y+=add;
sort(a+1,a+1+n);
for(int l=1,r=0;l<=n;l=r+1){
while(a[r+1].x==a[l].x&&r<=n)r++;
su=(LL)(r-l);sum=(LL)0;
for(int j=l;j<=r;j++)sum=(sum+a[j].y-a[l].y)%mod;
solve(l);
if(r>l)for(int j=l+1;j<=r;j++){
sum=(sum-su*(a[j].y-a[j-1].y)%mod+mod)%mod;
sum=(sum+(LL)(r-l+1-su)*(a[j].y-a[j-1].y)%mod+mod)%mod;
solve(j);su--;
}
for(int j=l;j<=r;j++)a1[a[j].y]++,a2[a[j].y]=(a2[a[j].y]+a[j].x)%mod;
}
printf("%lld\n",(ans%mod+mod)%mod);
return 0;
}