为什么有的大佬的时间只有70ms?我的270ms
查看原帖
为什么有的大佬的时间只有70ms?我的270ms
1019606
KouMoSir楼主2023/8/28 17:08

我自认为自己写的非常模板和规范了,没想到,一看提交有好多人用70ms就能通过,不知道还能怎样优化呢?

#include<iostream>
#include<iomanip>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10, mod = 99999997;
typedef long long ll;
ll a[N], b[N], ra[N], rb[N], rka[N], rkb[N], tmp[N], inda, indb, n, ans;
void merge(int b, int e) {
	if (b >= e)return;
	int mid = (b + e) / 2, l = b, r = mid + 1, ind = b;
	merge(l, mid), merge(mid + 1, e);
	while (l <= mid && r <= e) {
		if (rkb[l] < rkb[r])tmp[ind++] = rkb[l++];
		else {
			ans = (ans + mid - l + 1) % mod;
			tmp[ind++] = rkb[r++];
		}
	}
	while (l <= mid)tmp[ind++] = rkb[l++];
	while (r <= e)tmp[ind] = rkb[r++];
	for (int i = b; i < ind; i++)rkb[i] = tmp[i];
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++)cin >> a[i], ra[i] = a[i];
	for (int i = 1; i <= n; i++)cin >> b[i], rb[i] = b[i];
	sort(a + 1, a + 1 + n);
	sort(b + 1, b + 1 + n);
	for (int i = 1; i <= n; i++) {
		inda = lower_bound(a + 1, a + n + 1, ra[i]) - a - 1;
		indb = lower_bound(b + 1, b + n + 1, rb[i]) - b - 1;
		ra[i] = inda;
		rka[ra[i]] = i;
		rb[i] = indb;
	}
	for (int i = 1; i <= n; i++)rkb[i] = rka[rb[i]];
	merge(1, n);
	cout << ans % mod;
}
2023/8/28 17:08
加载中...