题目链接

评测记录

Code：

#include <bits/stdc++.h>
using namespace std;
const long long maxn = 5e5 + 5;
long long n, sum[maxn << 2], m;
struct node{
    double x, y, v;
}gun[maxn]; //炮弹
struct temp{
    long long p, x;
    bool operator <(const temp &a)const{
        return min(p, x) > min(a.p, a.x);
    }
}t[maxn];
inline long long FR(){
    long long res = 0;
    bool sign = 0;
    char ch = getchar();
    while((ch < '0' || ch > '9') && ch ^ '-')
        ch = getchar();
    if(ch == '-'){
        sign = 1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9'){
        res = (res << 3) + (res << 1) + (ch ^ 48);
        ch = getchar();
    }
    return sign ? -res : res;
}
void Build(long long rt, long long l, long long r){
    if(l == r){
        sum[rt] = 0;
        return;
    }
    long long mid = l + r >> 1;
    Build(rt << 1, l, mid);
    Build(rt << 1 | 1, mid + 1, r);
    sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}
void Modify(long long rt, long long l, long long r, long long pos){
    if(l == r){
        ++sum[rt];
        return;
    }
    long long mid = l + r >> 1;
    if(pos <= mid)
        Modify(rt << 1, l, mid, pos);
    else
        Modify(rt << 1 | 1, mid + 1, r, pos);
    sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}
long long Ask(long long rt, long long l, long long r, long long L, long long R){
    if(L <= l && R >= r)
        return sum[rt];
    long long ans = 0, mid = l + r >> 1;
    if(L <= mid)
        ans += Ask(rt << 1, l, mid, L, R);
    if(R > mid)
        ans += Ask(rt << 1 | 1, mid + 1, r, L, R);
    return ans;
}
double Calc(node x){ //计算落点
    return x.x + x.v * sqrt(x.y / 4.9);
}
map<double, vector<long long>>M;
long long p[maxn], a[maxn]; //p是威力，a是减少的威力值
bool cmp(long long x, long long y){
    return x > y;
}
bool cmp1(long long x, long long y){
    return gun[x].x < gun[y].x;
}
void DealY(vector<long long>v){
    sort(v.begin(), v.end(), cmp1);
    vector<long long>d;
    for(auto i : v)
        d.push_back((long long)Calc(gun[i]));
    vector<long long>id(d);
    sort(id.begin(), id.end());
    id.erase(unique(id.begin(), id.end()), id.end());
    long long len = id.size();
    Build(1, 1, len); //正反用两次线段树求值
    for(long long i = 0; i < d.size(); ++i){
        long long pos = lower_bound(id.begin(), id.end(), d[i]) - id.begin() + 1;
        p[v[i]] += Ask(1, 1, len, pos, len);
        Modify(1, 1, len, pos);
    }
    Build(1, 1, len);
    for(long long i = d.size() - 1; i >= 0; --i){
        long long pos = lower_bound(id.begin(), id.end(), d[i]) - id.begin() + 1;
        p[v[i]] += Ask(1, 1, len, 1, pos);
        Modify(1, 1, len, pos);
    }
}
void Read(){
    n = FR(), m = FR();
    for(long long i = 1; i <= n; ++i){
        gun[i] = {double(FR()), double(FR()), double(FR())};
        M[gun[i].y].push_back(i);
    }
    for(long long i = 1; i <= n; ++i)
        a[i] = FR();
}
void solve(){
    Read();
    for(auto i : M) //对每个y单独处理
        DealY(i.second);
    long long cnt = 0;
    for(long long i = 1; i <= n; ++i)
        t[i] = {p[i], a[i]};
    sort(t + 1, t + n + 1);
    for(long long i = 1; i <= n; ++i){ //贪心求结果
        if(m)
            cnt += max((long long)0, t[i].p - t[i].x), --m;
        else
            cnt += t[i].p;
    }
    printf("%lld", cnt);
}
int main(){
    solve();
    return 0;
}