319ms,快速幂+优先队列
查看原帖
319ms,快速幂+优先队列
712110
N0_1楼主2024/10/20 14:56
#include <bits/stdc++.h>

#define debug(x) cerr << #x << " = " << x << ' ';
#define please return
#define AC 0
#define RI register int
#define open(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout);
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)

using namespace std;

namespace LJW {
	// TODO quickly read
	inline char getch() { static char buf[1 << 17], *p = buf, *q = buf; return p == q && (q = buf + fread(p = buf, 1, 1 << 17, stdin), p == q) ? EOF : *p++;}
	template<typename T> inline void read(T &x) { x = 0; int f = 0;char ch = getch(); while (ch < '0' || ch > '9') {if (ch == '-') f = 1;ch = getch();} while (ch >= '0' && ch <= '9') {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getch();} if (f) x = (~x) + 1;}
	template<typename T, typename ... Args> inline void read(T &x, Args &... y){ read(x), read(y...); }
	template<typename T, typename F> inline void readn(T a[], F n) { for_each(a + 1, a + n + 1, [](T &x){ read(x); }); }
	// TODO quickly write
	template<typename T> inline void write(T x) { if (x < 0) { putchar('-'); x = -x; } if (x < 10) putchar(x ^ 48); else write(x / 10), putchar(x % 10 ^ 48);}
	template<typename T> inline void put(T x, char ch) { write(x); putchar(ch); }
	template<typename T, typename F> inline void printn(T a[], F n) { for_each(a + 1, a + n + 1, [](T &x) { put(x, ' '); }); putchar('\n'); }
	// TODO Math
	template<typename T> inline bool chkmax(T &x, T y) { return x < y ? x = y, 1: 0; }
	template<typename T> inline bool chkmin(T &x, T y) { return x > y ? x = y, 1: 0; }
	template<typename T> inline T qpow(T x, T y, T p) { T res = 1; while (y) { if (y & 1) res = res * x % p; x = x * x % p; y >>= 1; } return res % p; }
	template<typename T> inline T gcd(T x, T y) { return y ? gcd(y, x % y): x;}
	template<typename T> inline T lcm(T x, T y) { return x / gcd(x, y) * y; }
}

typedef long long LL;

using namespace LJW;

const int N = 2e5 + 10;
const LL p = 1e9 + 7;

LL a[N], b[N], limit = p;

LL inv(LL x) {
	return qpow(x, p - 2, p);
}

int main() {
	priority_queue<LL, vector<LL>, greater<LL> > pq;
	int n; read(n);
	readn(a, n); readn(b, n);
	for (int i = 1; i <= n; i++) {
		pq.push(min(b[i] - 1, a[i] - b[i]));
		limit = min(limit, max(b[i] - 1, a[i] - b[i]));
	}

	LL ans = 0, tk = 1;
	LL lst = pq.top();

	function<void(int)> func = [&](int op) -> void {
		LL tp = pq.top(); pq.pop();
		if (lst == tp && op) return ;
		tp = min(tp, limit);
		ans += qpow(2LL, 1LL * int(pq.size()) + 1, p) * (tp - tk + 1) % p; ans %= p;
		tk = tp + 1;
		lst = tp, tk = tp + 1;
		return ;
	};

	if (tk <= limit) func(0);
	
	while (pq.size() && tk <= limit) func(1);

	ans = ans + max(0LL, limit - tk + 1) % p;
	
	put((ans + 1) % p, '\n');

	// system("pause");
	please AC;
}

2024/10/20 14:56
加载中...