Submission #485890


Source Code Expand

Copy
#include<cstdio>
#include<utility>
#include<vector>
#include<algorithm>

using namespace std;

typedef pair<long long,long long> P;

const long long mod=1000000007;

int N;
long long ws[100100],hs[100100];

long long sum_w[100100];
long long sum_wh[100100];

long long fact[100100];
long long invs[100100];

P ps[100100];

long long sorted_hs[100100];
long long sorted_ws[100100];
vector<long long> uniq_hs;

long long ex(long long a,long long e){
	if(e==0) return 1;
	long long tmp=ex(a,e/2);
	tmp*=tmp;
	tmp%=mod;
	if(e%2==1) tmp*=a;
	tmp%=mod;
	return tmp;
}

long long inv(long long a){
	return ex(a,mod-2);
}
/*
long long func(int N,int j){
	if(N-j<0||N-j+1>N) return 0;
	long long num1=fact[N]*ifact[N-j];
	num1%=mod;
	long long num2=fact[N]*ifact[N-j+1];
	num2%=mod;
	long long res=num2-num1;
	res*=2;
	res%=mod;
	return res;
}*/

long long func(int N,int j){
	long long res=fact[N];
	res*=invs[j+1];
	res%=mod;
	if(j==0) return res;
	else return (res*2)%mod;
}

int count_higher_or_equal(long long x){
	int id=lower_bound(sorted_hs,sorted_hs+N,x)-sorted_hs;
	return N-id;
}

long long solve(){
	long long res=0;
	for(int j=1;j<uniq_hs.size();j++){
//		printf("j=%d\n",j);
		long long cur_h=uniq_hs[j];
//		printf("cur_h=%lld\n",cur_h);
		int cnt1=count_higher_or_equal(cur_h);
		int cnt2=count_higher_or_equal(cur_h+1);
//		printf("cnt=%d %d\n",cnt1,cnt2);
		long long coe=-func(N,cnt1)+func(N,cnt2);
//		printf("coe=%lld\n",coe);
//		printf("%lld %lld\n",func(N,cnt1),func(N,cnt2));
		int j_=lower_bound(sorted_hs,sorted_hs+N,uniq_hs[j]+1)-sorted_hs-1;
		long long coe2=sum_w[j_-1]*sorted_hs[j_]-sum_wh[j_-1];
		coe2%=mod;
		long long num=coe*coe2;
		num%=mod;
		res+=num;
		res%=mod;
	}
	return res;
}

void init(){
	for(int i=0;i<N;i++) ps[i]=P(hs[i],ws[i]);
	sort(ps,ps+N);
	for(int i=0;i<N;i++){
		sorted_hs[i]=ps[i].first;
		sorted_ws[i]=ps[i].second;
		uniq_hs.push_back(sorted_hs[i]);
	}
/*	printf("sorted_hs");
	for(int i=0;i<N;i++) printf("%lld\n",sorted_hs[i]);
	printf("\n");*/
	uniq_hs.erase(unique(uniq_hs.begin(),uniq_hs.end()),uniq_hs.end());
	sum_w[0]=sorted_ws[0];
	for(int i=1;i<N;i++){
		sum_w[i]=sum_w[i-1]+sorted_ws[i];
		sum_w[i]%=mod;
	}
	sum_wh[0]=sorted_hs[0]*sorted_ws[0];
	sum_wh[0]%=mod;
	for(int i=1;i<N;i++){
		sum_wh[i]=sum_wh[i-1]+sorted_hs[i]*sorted_ws[i];
		sum_wh[i]%=mod;
	}
	for(int i=0;i<=N;i++){
		invs[i]=inv(i);
	}
	fact[0]=1;
	for(int i=1;i<=N;i++){
		fact[i]=fact[i-1]*i;
		fact[i]%=mod;
	}
}

void input(){
	scanf("%d",&N);
	for(int i=0;i<N;i++){
		scanf("%lld%lld",ws+i,hs+i);
	}
}

int main(){
	input();
	init();
	long long ans=solve();
	ans%=mod;
	ans+=mod;
	ans%=mod;
	printf("%lld\n",ans);
	return 0;
}

Submission Info

Submission Time
Task E - 天下一コップ
User wo01
Language C++ (GCC 4.9.2)
Score 140
Code Size 2799 Byte
Status
Exec Time 182 ms
Memory 9544 KB

Compile Error

./Main.cpp: In function ‘void input()’:
./Main.cpp:123:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&N);
                ^
./Main.cpp:125:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld",ws+i,hs+i);
                              ^

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01.txt, sample_02.txt, sample_03.txt
Subtask1 15 / 15 sample_01.txt, sample_02.txt, sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt
Subtask2 55 / 55 sample_01.txt, sample_02.txt, sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask2_13.txt, subtask2_14.txt
Subtask3 70 / 70 sample_01.txt, sample_02.txt, sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask2_13.txt, subtask2_14.txt, subtask3_01.txt, subtask3_02.txt, subtask3_03.txt, subtask3_04.txt, subtask3_05.txt, subtask3_06.txt, subtask3_07.txt, subtask3_08.txt, subtask3_09.txt, subtask3_10.txt, subtask3_11.txt, subtask3_12.txt, subtask3_13.txt, subtask3_14.txt
Case Name Status Exec Time Memory
sample_01.txt 28 ms 2464 KB
sample_02.txt 27 ms 2440 KB
sample_03.txt 26 ms 2336 KB
subtask1_01.txt 27 ms 2332 KB
subtask1_02.txt 26 ms 2340 KB
subtask1_03.txt 25 ms 2336 KB
subtask1_04.txt 25 ms 2336 KB
subtask1_05.txt 26 ms 2344 KB
subtask1_06.txt 26 ms 2464 KB
subtask1_07.txt 26 ms 2344 KB
subtask1_08.txt 26 ms 2440 KB
subtask1_09.txt 28 ms 2336 KB
subtask1_10.txt 28 ms 2336 KB
subtask1_11.txt 28 ms 2376 KB
subtask1_12.txt 28 ms 2348 KB
subtask1_13.txt 27 ms 2340 KB
subtask1_14.txt 26 ms 2340 KB
subtask2_01.txt 27 ms 2588 KB
subtask2_02.txt 27 ms 2472 KB
subtask2_03.txt 28 ms 2464 KB
subtask2_04.txt 30 ms 2464 KB
subtask2_05.txt 30 ms 2584 KB
subtask2_06.txt 30 ms 2584 KB
subtask2_07.txt 28 ms 2592 KB
subtask2_08.txt 30 ms 2588 KB
subtask2_09.txt 30 ms 2472 KB
subtask2_10.txt 28 ms 2464 KB
subtask2_11.txt 27 ms 2456 KB
subtask2_12.txt 28 ms 2472 KB
subtask2_13.txt 29 ms 2464 KB
subtask2_14.txt 28 ms 2588 KB
subtask3_01.txt 127 ms 9500 KB
subtask3_02.txt 151 ms 9544 KB
subtask3_03.txt 182 ms 9364 KB
subtask3_04.txt 172 ms 9100 KB
subtask3_05.txt 172 ms 9104 KB
subtask3_06.txt 170 ms 8996 KB
subtask3_07.txt 178 ms 9364 KB
subtask3_08.txt 169 ms 8988 KB
subtask3_09.txt 169 ms 8984 KB
subtask3_10.txt 180 ms 9492 KB
subtask3_11.txt 149 ms 9104 KB
subtask3_12.txt 155 ms 9240 KB
subtask3_13.txt 150 ms 9192 KB
subtask3_14.txt 157 ms 9504 KB