提出 #26422869

---

ソースコード 拡げる

#include <stdio.h>
#include <stdlib.h>
 
#define MOD_BY 1000000007
 
int cmp(const void* x, const void* y) {
	int a = *(const int*)x, b = *(const int*)y;
	return a < b ? -1 : a > b;
}
 
int N, M;
int A[212345];
int B[212345];
 
int left_count[212345], right_count[212345];
int next_differ[212345];
 
long long right_count_sum[212345];
 
int main(void) {
	int i;
	int pos;
	int ans = 0;
	if (scanf("%d%d", &N, &M) != 2) return 1;
	for (i = 0; i < N; i++) {
		if (scanf("%d", &A[i]) != 1) return 1;
	}
	for (i = 0; i < M; i++) {
		if (scanf("%d", &B[i]) != 1) return 1;
	}
	qsort(A, N, sizeof(*A), cmp);
	qsort(B, M, sizeof(*B), cmp);
	for (i = N - 1, pos = M; i >= 0; i--) {
		while (pos > 0 && A[i] < B[pos - 1]) pos--;
		right_count[i] = M - pos;
	}
	for (i = 0, pos - 0; i < N; i++) {
		while (pos < M && B[pos] < A[i]) pos++;
		left_count[i] = pos;
	}
	next_differ[N - 1] = N;
	for (i = N - 2, pos = N; i >= 0; i--) {
		if (A[i] != A[i + 1]) pos = i + 1;
		next_differ[i] = pos;
	}
	for (i = N - 1; i >= 0; i--) {
		right_count_sum[i] = right_count_sum[i + 1] + right_count[i];
	}
	for (i = 0; i < N; i++) {
		ans = (int)((ans + left_count[i] * (right_count_sum[next_differ[i]] % MOD_BY)) % MOD_BY);
	}
#if 0
	/* debug */
	for (i = 0; i < N; i++) {
		printf(" %d", left_count[i]);
	}
	puts("");
	for (i = 0; i < N; i++) {
		printf(" %d", right_count[i]);
	}
	puts("");
	for (i = 0; i < N; i++) {
		printf(" %d", (int)right_count_sum[i]);
	}
	puts("");
#endif
	printf("%d\n", ans);
	return 0;
}

#include <stdio.h>
#include <stdlib.h>

#define MOD_BY 1000000007

int cmp(const void* x, const void* y) {
	int a = *(const int*)x, b = *(const int*)y;
	return a < b ? -1 : a > b;
}

int N, M;
int A[212345];
int B[212345];

int left_count[212345], right_count[212345];
int next_differ[212345];

long long right_count_sum[212345];

int main(void) {
	int i;
	int pos;
	int ans = 0;
	if (scanf("%d%d", &N, &M) != 2) return 1;
	for (i = 0; i < N; i++) {
		if (scanf("%d", &A[i]) != 1) return 1;
	}
	for (i = 0; i < M; i++) {
		if (scanf("%d", &B[i]) != 1) return 1;
	}
	qsort(A, N, sizeof(*A), cmp);
	qsort(B, M, sizeof(*B), cmp);
	for (i = N - 1, pos = M; i >= 0; i--) {
		while (pos > 0 && A[i] < B[pos - 1]) pos--;
		right_count[i] = M - pos;
	}
	for (i = 0, pos - 0; i < N; i++) {
		while (pos < M && B[pos] < A[i]) pos++;
		left_count[i] = pos;
	}
	next_differ[N - 1] = N;
	for (i = N - 2, pos = N; i >= 0; i--) {
		if (A[i] != A[i + 1]) pos = i + 1;
		next_differ[i] = pos;
	}
	for (i = N - 1; i >= 0; i--) {
		right_count_sum[i] = right_count_sum[i + 1] + right_count[i];
	}
	for (i = 0; i < N; i++) {
		ans = (int)((ans + left_count[i] * (right_count_sum[next_differ[i]] % MOD_BY)) % MOD_BY);
	}
#if 0
	/* debug */
	for (i = 0; i < N; i++) {
		printf(" %d", left_count[i]);
	}
	puts("");
	for (i = 0; i < N; i++) {
		printf(" %d", right_count[i]);
	}
	puts("");
	for (i = 0; i < N; i++) {
		printf(" %d", (int)right_count_sum[i]);
	}
	puts("");
#endif
	printf("%d\n", ans);
	return 0;
}

提出情報

ジャッジ結果