QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#117581#5433. Absolute DifferenceUrgantTeam#WA 2ms7768kbC++234.8kb2023-07-01 18:41:492023-07-01 18:41:52

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-01 18:41:52]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:7768kb
  • [2023-07-01 18:41:49]
  • 提交

answer

#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define x first
#define y second

using namespace std;

typedef long double ld;
typedef long long ll;

pair <ll, ll> alice[100005], bob[100005];
ld pref_dif[100005], pref_square[100005], suf_dif[100005], suf_square[100005];
ld opa[100005];

ld pref_dis[100005], suf_dis[100005];

ld process(ll l, ll r, ll L, ll R)
{
 	if (l > L) swap(l, L), swap(r, R);

 	if (r <= L) return (ld) (r - l) * (R - L) * (R + L - r - l) / 2;
 	
 	if (r <= R)
 	{
 		ld fir = (ld) (r - L) * (L - l) * (r - l) / 2;
 		ld sec = (ld) (L - l) * (R - r) * (R + r - L - l) / 2;
 		ld third = (ld) (r - L) * (r - L) * (r - L) / 3;
 		ld four = (ld) (r - L) * (R - r) * (R - L) / 2;
 		return fir + sec + third + four;
 	}
 	else
 	{
 		ld fir = (ld) (L - l) * (R - L) * (R - l) / 2;
 		ld sec = (ld) (R - L) * (R - L) * (R - L) / 3;
 		ld third = (ld) (r - R) * (R - L) * (r - L) / 2;
 		return fir + sec + third;
 	}
}

ld process_pt_seg(ll x, ll l, ll r)
{
 	if (x < l) return ((ld) r * r - (ld) l * l) / 2 - (ld) x * (r - l);
 	if (x > r) return (ld) x * (r - l) - ((ld) r * r - (ld) l * l) / 2;

 	return (ld) (x - l) * (x - l) / 2 + (ld) (r - x) * (r - x) / 2;
}

int main()
{
 	//freopen("input.txt", "r", stdin);
 	//freopen("output.txt", "w", stdout);
	ios_base::sync_with_stdio(0); cin.tie(0);
	cout.precision(20);

	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> alice[i].x >> alice[i].y;
	for (int i = 1; i <= m; i++) cin >> bob[i].x >> bob[i].y;

	ll len_a = 0, len_b = 0;
	for (int i = 1; i <= n; i++) len_a += alice[i].y - alice[i].x;
	for (int i = 1; i <= m; i++) len_b += bob[i].y - bob[i].x;

	if (len_a == 0 && len_b == 0)
	{
	 	for (int i = 1; i <= m; i++) pref_dis[i] = pref_dis[i - 1] + bob[i].x;
	 	for (int i = m; i > 0; i--) suf_dis[i] = suf_dis[i + 1] + bob[i].x;
	 	
	 	int lef = 0;
	 	ld ans = 0;
	 	for (int i = 1; i <= n; i++)
	 	{
	 	 	while (lef < m && bob[lef + 1].x <= alice[i].x) lef++;

	 		ld sum1 = pref_dis[lef], sum2 = suf_dis[lef + 1];
	 		ans += (ld) lef * alice[i].x - sum1;
	 		ans += sum2 - (ld) (m - lef) * alice[i].x;
	 	}
	 	ans = ans / n / m;
	 	cout << fixed << ans << '\n';
	 	return 0;
	}

	if (len_b == 0)
	{
	 	for (int i = 1; i <= max(n, m); i++) swap(alice[i], bob[i]);
	 	swap(n, m);
	 	swap(len_a, len_b);
	}

	for (int i = 1; i <= m; i++) pref_dif[i] = pref_dif[i - 1] + (bob[i].y - bob[i].x);
	for (int i = 1; i <= m; i++) pref_square[i] = pref_square[i - 1] + (ld) bob[i].y * bob[i].y - (ld) bob[i].x * bob[i].x;
	for (int i = m; i > 0; i--) suf_dif[i] = suf_dif[i + 1] + (bob[i].y - bob[i].x);
	for (int i = m; i > 0; i--) suf_square[i] = suf_square[i + 1] + (ld) bob[i].y * bob[i].y - (ld) bob[i].x * bob[i].x;
	for (int i = 1; i <= m; i++)
	{
	 	opa[i] = opa[i - 1];
	 	ld s = (bob[i].y - bob[i].x);
	 	s = s * s * s / 3;
	 	ld t = (ld) bob[i].x * bob[i].y * (bob[i].y - bob[i].x);
	 	opa[i] += t + s;
	}

	if (len_a == 0)
	{
		ld ans = 0;
		int lef = 0, rig = 1;
		for (int i = 1; i <= n; i++)
		{
			while (lef < m && bob[lef + 1].y <= alice[i].x) lef++;
			while (rig <= m && bob[rig].x <= alice[i].x) rig++;

			ld left_part = (ld) alice[i].x * pref_dif[lef] - pref_square[lef] / 2;
			ld right_part = suf_square[rig] / 2 - (ld) alice[i].x * suf_dif[rig];
			ans += left_part + right_part;
			if (lef != rig - 1)
			{
			 	int A = lef + 1;
				ans += process_pt_seg(alice[i].x, bob[A].x, bob[A].y);
			}
		}
		ans = ans / n / len_b;
		cout << fixed << ans << '\n';
		return 0;
	}

	ld ans = 0;
	int lef = 0, rig = 1;
	for (int i = 1; i <= n; i++)
	{
		if (alice[i].x == alice[i].y) continue;

		while (lef < m && bob[lef + 1].y <= alice[i].x) lef++;
		while (rig <= m && bob[rig].x < alice[i].y) rig++;

		ld sum_left = (ld) (alice[i].x + alice[i].y) * pref_dif[lef] - pref_square[lef];
	 	ld left_part = (ld) (alice[i].y - alice[i].x) / 2 * sum_left;

	 	ld sum_right = suf_square[rig] - (ld) (alice[i].x + alice[i].y) * suf_dif[rig];
	 	ld right_part = (ld) (alice[i].y - alice[i].x) / 2 * sum_right;

	 	ans += left_part + right_part;

	 	if (lef == rig - 1) continue;

	 	int L = lef + 1, R = rig - 1;
	 	ans += process(alice[i].x, alice[i].y, bob[L].x, bob[L].y);
	 	if (L != R) ans += process(alice[i].x, alice[i].y, bob[R].x, bob[R].y);

	 	if (R > L + 1)
	 	{
	 	 	int mid_lef = L + 1, mid_rig = R - 1;
	 	 	ld fir = opa[mid_rig] - opa[mid_lef - 1];
	 	 	ld sec = (pref_square[mid_rig] - pref_square[mid_lef - 1]) / 2;
	 	 	ld third = (pref_dif[mid_rig] - pref_dif[mid_lef - 1]) / 2;
	 	 	ld A = (ld) alice[i].x * alice[i].x + (ld) alice[i].y * alice[i].y;
	 	 	ld B = alice[i].x + alice[i].y;
	 	 	ld middle_part = A * third - B * sec + fir;
	 	 	ans += middle_part;
	 	}
	}
	ans = ans / len_a / len_b;

	cout << fixed << ans << '\n';
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 5696kb

input:

1 1
0 1
0 1

output:

0.33333333333333333334

result:

ok found '0.333333333', expected '0.333333333', error '0.000000000'

Test #2:

score: 0
Accepted
time: 2ms
memory: 7652kb

input:

1 1
0 1
1 1

output:

0.50000000000000000000

result:

ok found '0.500000000', expected '0.500000000', error '0.000000000'

Test #3:

score: 0
Accepted
time: 1ms
memory: 7764kb

input:

1 1
-1000000000 1000000000
-1000000000 1000000000

output:

666666666.66666666668606922030

result:

ok found '666666666.666666627', expected '666666666.666666627', error '0.000000000'

Test #4:

score: 0
Accepted
time: 2ms
memory: 7736kb

input:

1 1
-1000000000 0
0 1000000000

output:

1000000000.00000000000000000000

result:

ok found '1000000000.000000000', expected '1000000000.000000000', error '0.000000000'

Test #5:

score: 0
Accepted
time: 2ms
memory: 7768kb

input:

1 1
-1000000000 -1000000000
-1000000000 1000000000

output:

1000000000.00000000000000000000

result:

ok found '1000000000.000000000', expected '1000000000.000000000', error '0.000000000'

Test #6:

score: 0
Accepted
time: 1ms
memory: 5716kb

input:

1 1
-999999999 1000000000
-1000000000 -1000000000

output:

1000000000.50000000000000000000

result:

ok found '1000000000.500000000', expected '1000000000.500000000', error '0.000000000'

Test #7:

score: 0
Accepted
time: 1ms
memory: 7752kb

input:

1 1
-1000000000 1000000000
-999999999 -999999999

output:

999999999.00000000052386894822

result:

ok found '999999999.000000000', expected '999999999.000000000', error '0.000000000'

Test #8:

score: 0
Accepted
time: 2ms
memory: 7744kb

input:

1 1
1000000000 1000000000
-1000000000 -1000000000

output:

2000000000.00000000000000000000

result:

ok found '2000000000.000000000', expected '2000000000.000000000', error '0.000000000'

Test #9:

score: -100
Wrong Answer
time: 2ms
memory: 5820kb

input:

1000 1000
-2175 -2174
-1068 -1065
-1721 -1718
777 834
1162 1169
-3529 -3524
3966 3993
1934 1952
-234 -223
-4967 -4947
8500 8510
5272 5276
-6048 -6033
-34 -22
700 705
-7890 -7886
5538 5543
4114 4126
-9201 -9162
-1521 -1519
-5103 -5100
439 441
993 997
-1684 -1680
-8413 -8404
6724 6728
-3242 -3239
2616...

output:

230.38872461632317342750

result:

wrong answer 1st numbers differ - expected: '6717.1171457', found: '230.3887246', error = '0.9657012'