归并求逆序对 10pts
查看原帖
归并求逆序对 10pts
765883
__Tao__楼主2022/10/23 20:51
#include <bits/stdc++.h>
#define ll long long
#define copy rt
using namespace std;
const int N = 5e5 + 5, g = 9.8;
int n, m, lb[N], cnt;
map<double, int>la;
ll ans;

struct Node {
	int x, y, v, a, p;
	double t1;
} r[N], bf[N];

bool cmp1(Node a, Node b) {
	return a.y == b.y ? a.x < b.x : a.y < b.y;
}

bool cmp2(Node a, Node b) {
	return a.a > b.a;
}

inline void copy(int a, int b, bool k) {
	if (k) {
		r[a].a = bf[b].a;
		r[a].x = bf[b].x;
		r[a].y = bf[b].y;
		r[a].v = bf[b].v;
		r[a].p = bf[b].p;
		r[a].t1 = bf[b].t1;
	} else {
		bf[a].a = r[b].a;
		bf[a].x = r[b].x;
		bf[a].y = r[b].y;
		bf[a].v = r[b].v;
		bf[a].p = r[b].p;
		bf[a].t1 = r[b].t1;
	}
}

void ms(int l, int ri) {
	if (l == ri)
		return;
	int m = l + ri >> 1, p = l, i = l, j = m + 1;
	ms(l, m);
	ms(m + 1, ri);
	while (i <= m && j <= ri) {
		if (r[i].t1 > r[j].t1) {
			r[j].p += m - i + 1;
			copy(p++, j++, 0);
		} else {
			r[i].p += j - m - 1;
			copy(p++, i++, 0);
		}
	}
	while (i <= m) {
		r[i].p += j - m - 1;
		copy(p++, i++, 0);
	}
	while (j <= ri) {
		r[j].p += m - i + 1;
		copy(p++, j++, 0);
	}
	for (int i = l; i <= ri; i++)
		copy(i, i, 1);
}

int main() {
	//freopen("missile4.in", "r", stdin);
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) {
		scanf("%d%d%d", &r[i].x, &r[i].y, &r[i].v);
		r[i].t1 = r[i].x + sqrt(r[i].y * 2.0 / g) * r[i].v;
	}
	sort(r + 1, r + n + 1, cmp1);
	int j = 1;
	for (int i = 2; i <= n; i++) {
		if (r[i].y != r[i - 1].y) {
			ms(j, i - 1);
			j = i;
		}
	}
	ms(j, n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &r[i].a);
		if (r[i].a > r[i].p)
			r[i].a = r[i].p;
		ans += r[i].p;
	}
	sort(r + 1, r + n + 1, cmp2);
	for (int i = 1; i <= m; i++) {
		ans -= r[i].a;
	}
	printf("%lld", ans);
	return 0;
}
2022/10/23 20:51
加载中...