30分代码求调
查看原帖
30分代码求调
590925
_x_y_楼主2022/10/25 20:49
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int N = 5e5 + 10;
int read(){
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar();
    return x*f;
}
struct node{
	int x1, y, x2id;
	double x2;
	int id;
	int weili;
}a[N];
int n, m, b[N];
int c[N];
int ask(int x){
	int ans = 0;
	for(; x; x -= x & -x)
		ans += c[x];
	return ans;
}
void add(int x, int y){
	for(; x <= N; x += x & -x)
		c[x] += y;
}
bool cmp1(node xx, node yy){
	if(abs(xx.x2 - yy.x2) <= 0.001)
		return xx.x1 > yy.x1;
	return xx.x2 < yy.x2;
}
bool cmp2(node xx, node yy){
	if(xx.y != yy.y)
		return xx.y < yy.y;
	return xx.x1 < yy.x1;
}
bool cmp3(int xx, int yy){
	return xx > yy;
}
bool cmp4(node xx, node yy){
	return xx.id < yy.id;
}
int main(){
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		a[i].x1 = read();
		a[i].y = read();
		int v = read();
		a[i].x2 = 1.0 * a[i].x1 + 1.0 * v * sqrt(2.0 * a[i].y / 9.8);
		a[i].id = i;
	}
	sort(a + 1, a + n + 1, cmp1);
	for(int i = 1; i <= n; i++)
		a[i].x2id = i;
	sort(a + 1, a + n + 1, cmp2);
	long long ans = 0;
	for(int i = 1; i <= n; i++){
		int j;
		for(j = i; j <= n && a[j].y == a[i].y; j++)
			;
		j--;
		memset(c, 0, sizeof(c));
		for(int ii = j; ii >= i; ii--){
			int t = ask(a[ii].x2id - 1);
			a[ii].weili += t;
			add(a[ii].x2id, 1);
		}
		memset(c, 0, sizeof(c));
		for(int ii = i; ii <= j; ii++){
			int t = ask(n) - ask(a[ii].x2id);
			a[ii].weili += t;
			add(a[ii].x2id, 1);
		}
		i = j + 1;
	}
	for(int i = 1; i <= n; i++)
		ans += a[i].weili;
	sort(a + 1, a + n + 1, cmp4);
	for(int i = 1; i <= n; i++){
		b[i] = read();
		b[i] = min(b[i], a[i].weili);
	}
	sort(b + 1, b + n + 1, cmp3);
	for(int i = 1; i <= m && i <= n; i++)
		ans -= b[i];
	cout << ans << endl;
	return 0;
}
/*
10 3
3 7 -3
7 7 8
1 7 -9
-8 7 4
-4 7 -2
1 3 1
-5 7 0
-2 3 9
9 7 5
0 3 7
6 8 10 7 2 5 4 2 8 5
*/
//6 
2022/10/25 20:49
加载中...