MnZn刚学OI,90分,WA2点,求调
查看原帖
MnZn刚学OI,90分,WA2点,求调
253936
simonG楼主2022/10/24 11:14
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=5e5+10;
const double g=9.8;
int n,w,z[N],mb,mc,b[N],p[N],tr[N];
double c[N];
LL ans;
vector<int> v[N];
struct node {
	int x,y,v;
	double x0;
} a[N];
bool cmp(int p,int q) {
	return a[p].x<a[q].x;
}
void modify(int p,int x) {
	for(; p<N; p+=p&-p) tr[p]+=x;
}
int query(int p) {
	int res=0;
	for(; p; p-=p&-p) res+=tr[p]; 
	return res;
}
int main() {
	freopen("missile4.in","r",stdin);
	scanf("%d%d",&n,&w);
	for(int i=1; i<=n; i++) {
		scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].v);
		a[i].x0=a[i].x+(double)a[i].v*sqrt(2*a[i].y/g);
		b[i]=a[i].y; c[i]=a[i].x0;
	}
	sort(b+1,b+1+n); sort(c+1,c+1+n);
	mb=unique(b+1,b+1+n)-b; mc=unique(c+1,c+1+n)-c;
	for(int i=1; i<=n; i++) {
		a[i].y=lower_bound(b+1,b+1+mb,a[i].y)-b;
		a[i].x0=lower_bound(c+1,c+1+mc,a[i].x0)-c;
		v[a[i].y].push_back(i);
	}
	for(int i=1; i<=mb; i++) {
		sort(v[i].begin(),v[i].end(),cmp);
		for(int j=0; j<v[i].size(); j++) {
			p[v[i][j]]+=j-query(a[v[i][j]].x0);
			modify(a[v[i][j]].x0,1);
		}
		for(int j=0; j<v[i].size(); j++) 
			modify(a[v[i][j]].x0,-1);
		for(int j=v[i].size()-1; j>=0; j--) {
			p[v[i][j]]+=query(a[v[i][j]].x0);
			modify(a[v[i][j]].x0,1);
		}
		for(int j=v[i].size()-1; j>=0; j--) 
			modify(a[v[i][j]].x0,-1);
	}
	for(int i=1; i<=n; i++) {
		scanf("%d",&z[i]);
		z[i]=min(z[i],p[i]);
		ans=ans+1ll*p[i];
	}
	sort(z+1,z+1+n);
	for(int i=n; i>=n-w+1; i--) ans=ans-1ll*z[i];
	printf("%lld\n",ans);
	return 0;
}
2022/10/24 11:14
加载中...