92分WA求调
查看原帖
92分WA求调
785657
jun666楼主2024/10/20 19:13
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5, M = 1e9 + 7;
ll ksm(ll a, ll p) {
	ll res = 1;
	while (p) {
		if (p & 1)
			(res *= a) %= M;
		(a *= a) %= M;
		p >>= 1;
	}
	return res;
}
ll n, b[2 * N], a[N][2], d[2 * N], cnt[2 * N], mul[2 * N], tot, ans, mi = 1e18;
int num[2 * N], ord[N][2];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> b[i];
	for (int i = 0; i < n; i++) {
		int c;
		cin >> c;
		num[i * 2] = a[i][0] = b[i] - c, num[i * 2 + 1] = a[i][1] = c - 1;
		mi = min(max(a[i][0], a[i][1]), mi);
		b[i] = 0;
	}
	sort(num, num + 2 * n);
	tot = unique(num, num + 2 * n) - num;
	for (int i = 0; i < n; i++) {
		ord[i][0] = lower_bound(num, num + tot, a[i][0]) - num;
		ord[i][1] = lower_bound(num, num + tot, a[i][1]) - num;
	}
	for (int i = 0; i < n; i++) {
		int tmp = min(ord[i][0], ord[i][1]);
		if (tmp > 0)
			d[tmp - 1]++;
		if (ord[i][0] == ord[i][1]) {
			mul[tmp]++;
		} else {
			int o1 = ord[i][0], o2 = ord[i][1];
			(b[o1] += ksm(2, cnt[o1])) %= M;
			cnt[o1]++;
			(b[o2] += ksm(2, cnt[o2])) %= M;
			cnt[o2]++;
		}
	}
	ll tmp = 0;
	for (int i = tot; i >= 0; i--) {
		tmp += d[i];
		mul[i] += tmp;
	}
	for (int i = 0; i < tot; i++) {
		tmp = ksm(2, mul[i]);
		if (!b[i] && mul[i] > 0)
			b[i] = 1;
		(tmp *= b[i]) %= M;
		(tmp *= num[i]) %= M;
		if (num[i] > mi)
			tmp = 0;
		(ans += tmp) %= M;
	}
	cout << ans + 1 << '\n';
	return 0;
}
2024/10/20 19:13
加载中...