QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#607863#5433. Absolute Differencelonelywolf#RE 1ms4060kbC++205.1kb2024-10-03 16:47:332024-10-03 16:47:33

Judging History

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

  • [2024-10-03 16:47:33]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:4060kb
  • [2024-10-03 16:47:33]
  • 提交

answer

#include <bits/stdc++.h>  
using namespace std;  

#define int long long  

using db = long double;

#define fi first
#define se second

signed main() {  
    ios::sync_with_stdio(false);
    cin.tie(nullptr);  

    cout << fixed << setprecision(20);

	int n, m;
	cin >> n >> m;

	vector<pair<int, int>> a(n), b(m);
	for (auto &[l, r] : a) {
		cin >> l >> r;
	}
	for (auto &[l, r] : b) {
		cin >> l >> r;
	}

	sort(a.begin(), a.end());
	sort(b.begin(), b.end());
	
	auto check = [&](const vector<pair<int, int>> &t) {
		for (auto [x, y] : t) {
			if (x != y) {
				return true;
			}
		}
		return false;
 	};

 	auto work = [&](const vector<pair<int, int>> &t) {
 		vector<pair<int, int>> ret;
 		for (auto [x, y] : t) {
 			if (x != y) {
 				ret.push_back({x, y});
 			}
 		}
 		return ret;
 	};

 	bool oka = check(a), okb = check(b);
 	if (oka) {
 		a = work(a);
 		n = a.size(); 
 	} 
 	if (okb) {
 		b = work(b);
 		m = b.size();
 	}

 	if (!oka && !okb) {
 		db mid = 0;
 		for (auto [x, y] : b) {
 			mid += x;
 		}
 		mid /= m;
 		db ans = 0;
 		for (auto [x, y] : a) {
 			ans += abs(mid - x);
 		}
 		ans /= n;
 		assert(false);
 		cout << ans << "\n";
 		return 0;
 	}

 	if (oka && !okb) {
 		swap(oka, okb);
 		swap(a, b);
 	}

 	if (!oka && okb) {
 		set<int> s;
 		for (auto [x, y] : a) {
 			s.insert(x);
 		}
 		for (auto [x, y] : b) {
 			s.insert(x);
 			s.insert(y);
 		}
 		vector<int> p(s.begin(), s.end());

 		vector<pair<int, int>> nb;
 		db L = 0;
 		for (int i = 1; i < p.size(); i++) {
 			int x = p[i - 1], y = p[i];
 			int l = -1, r = m;
 			while (l + 1 != r) {
 				int mid = (l + r) / 2;
 				if (b[mid].fi <= x) {
 					l = mid;
 				} else {
 					r = mid;
 				}
 			}
 			if (l == -1 || b[l].se < y) {
 				continue;
 			}
 			nb.push_back({x, y});
 			L += (y - x);
 		}
 		b = nb;
 		m = b.size();
 		vector<db> s1(m + 1), s2(m + 1);
 		for (int i = 1; i <= m; i++) {
 			s1[i] = s1[i - 1] + (b[i - 1].se - b[i - 1].fi);
 			s2[i] = s2[i - 1] + 1.0 * (b[i - 1].se - b[i - 1].fi) * (b[i - 1].fi + b[i - 1].se) / 2;
 		}
 		auto qry1 = [&](int ql, int qr) {
 			return s1[qr] - s1[ql - 1];
 		};
 		auto qry2 = [&](int ql, int qr) {
 			return s2[qr] - s2[ql - 1];
 		};
 		db ans = 0;
 		for (auto [x, y] : a) {
 			int l = -1, r = m;
 			while (l + 1 != r) {
 				int mid = (l + r) / 2;
 				if (b[mid].se <= x) {
 					l = mid;
 				} else {
 					r = mid;
 				}
 			}
 			if (l == -1) {
 				continue;
 			}
 			ans += x * qry1(1, l + 1) - qry2(1, l + 1);	
 		}
 		for (auto [x, y] : a) {
 			int l = -1, r = m;
 			while (l + 1 != r) {
 				int mid = (l + r) / 2;
 				if (b[mid].fi >= x) {
 					r = mid;
 				} else {
 					l = mid;
 				}
 			}
 			if (r == m) {
 				continue;
 			}
 			ans += qry2(r + 1, m) - x * qry1(r + 1, m);	
 		}

 		ans /= n;
 		ans /= L;
 	
 		cout << ans << "\n";
 		return 0;
 	}

 	set<int> s;
	for (auto [x, y] : a) {
		s.insert(x);
		s.insert(y);
	}
	for (auto [x, y] : b) {
		s.insert(x);
		s.insert(y);
	}

	vector<int> p(s.begin(), s.end());

	vector<pair<int, int>> na;
	vector<pair<int, int>> nb;
	
	db La = 0, Lb = 0;
	for (int i = 1; i < p.size(); i++) {
		int x = p[i - 1], y = p[i];
		int l = -1, r = m;
		while (l + 1 != r) {
			int mid = (l + r) / 2;
			if (a[mid].fi <= x) {
				l = mid;
			} else {
				r = mid;
			}
		}
		if (l == -1 || a[l].se < y) {
			continue;
		}
		na.push_back({x, y});
		La += (y - x);
	}
	for (int i = 1; i < p.size(); i++) {
		int x = p[i - 1], y = p[i];
		int l = -1, r = m;
		while (l + 1 != r) {
			int mid = (l + r) / 2;
			if (b[mid].fi <= x) {
				l = mid;
			} else {
				r = mid;
			}
		}
		if (l == -1 || b[l].se < y) {
			continue;
		}
		nb.push_back({x, y});
		Lb += (y - x);
	}

	a = na;
	n = a.size();
	b = nb;
	m = b.size();

	set<pair<int, int>> sb;
	for (auto [x, y] : b) {
		sb.insert({x, y});
	}

	vector<db> s1(m + 1), s2(m + 1);
	for (int i = 1; i <= m; i++) {
		s1[i] = s1[i - 1] + (b[i - 1].se - b[i - 1].fi);
		s2[i] = s2[i - 1] + 1.0 * (b[i - 1].se - b[i - 1].fi) * (b[i - 1].fi + b[i - 1].se) / 2;
	}

	auto qry1 = [&](int ql, int qr) {
		return s1[qr] - s1[ql - 1];
	};
	auto qry2 = [&](int ql, int qr) {
		return s2[qr] - s2[ql - 1];
	};
	
	db ans = 0;
	for (auto [x, y] : a) {
		if (sb.count({x, y})) {
			ans += 1.0 * (y - x) * (y - x) * (y - x) / 3;
		}
	}

	for (auto [x, y] : a) {
		int l = -1, r = m;
		while (l + 1 != r) {
			int mid = (l + r) / 2;
			if (b[mid].se <= x) {
				l = mid;
			} else {
				r = mid;
			}
		}
		if (l == -1) {
			continue;
		}
		ans += (y - x) * (0.5 * (x + y) * qry1(1, l + 1) - qry2(1, l + 1));	
	}
	for (auto [x, y] : a) {
		int l = -1, r = m;
		while (l + 1 != r) {
			int mid = (l + r) / 2;
			if (b[mid].fi >= y) {
				r = mid;
			} else {
				l = mid;
			}
		}
		if (r == m) {
			continue;
		}
		ans += (y - x) * (qry2(r + 1, m) - 0.5 * (x + y) * qry1(r + 1, m)) ;	
	}

	ans /= La, ans /= Lb;

	cout << ans << "\n";

    return 0;
}  
  

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

1 1
0 1
0 1

output:

0.33333333333333331483

result:

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

Test #2:

score: 0
Accepted
time: 0ms
memory: 4060kb

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: 0ms
memory: 3768kb

input:

1 1
-1000000000 1000000000
-1000000000 1000000000

output:

666666666.66666662966599687934

result:

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

Test #4:

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

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: 0ms
memory: 3992kb

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: 4056kb

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: 3832kb

input:

1 1
-1000000000 1000000000
-999999999 -999999999

output:

999999999.00000000052386894822

result:

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

Test #8:

score: -100
Runtime Error

input:

1 1
1000000000 1000000000
-1000000000 -1000000000

output:


result: