社区讨论

有码量少的写法吗?

P8593「KDOI-02」一个弹的投参与者 8已保存回复 13

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
13 条
当前快照
1 份
快照标识符
@lo7qu60l
此快照首次捕获于
2023/10/27 06:16
2 年前
此快照最后确认于
2023/10/27 06:16
2 年前
查看原帖
顺便说一句(交了freopen的保龄了)
CPP
#include<bits/stdc++.h>
#define ll long long
using namespace std;
namespace Mashiro {
    char buf[1<<18],*p1=buf,*p2=buf;
    inline int getc() {
        return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<18,stdin),p1==p2)?EOF:*p1++;
    }
    template<typename T>inline void read(T& x) {
        x=0;int f=1;
        char ch=getc();
        while(!isdigit(ch)){if(ch=='-')f=~f+1;ch=getc();}
        while (isdigit (ch)) {x=(x<<3)+(x<<1)+(ch^48);ch=getc();}
        x*=f;
    }
    template <typename T,typename... Args> inline void read(T& x, Args&... args) {
        read(x);
        read(args...);
    }
    char buffer[1<<18];int p11=-1;const int p22=(1<<18)-1;
    inline void flush() {fwrite(buffer,1,p11+1,stdout),p11=-1;}
    inline void putc(const char &x) {if (p11==p22) flush();buffer[++p11]=x;}
    template<typename T>inline void write(T x) {
        static int buf[40],top=0;
        if(x<0)putc('-'),x=~x+1;
        while(x)buf[++top]=x%10,x/=10;
        if(top==0)buf[++top]=0;
        while (top) putc(buf[top--]^48);
        putc(' ');
        flush();
     }
     template <typename T,typename... Args> inline void write(T x, Args... args) {
         write(x);
         write(args...);
     }
}
namespace Misaka{
    auto seed=std::chrono::system_clock::now().time_since_epoch().count();
    std::mt19937 rnd(seed);
    template<typename T>T random(T l, T r) {
    	 return std::uniform_int_distribution<T>(l,r)(rnd); 
    }
}
namespace Cmp{
    template<typename T>inline T Min(T a,T b){
        return a>b?b:a;
    }
    template<typename T,typename... Args> inline T Min(T a,T b,Args... args){
        return Min(a,Min(b,args...));
    }
    template<typename T>inline T Max(T a,T b){
        return a>b?a:b;
    }
    template<typename T,typename... Args> inline T Max(T a,T b,Args... args){
        return Max(a,Max(b,args...));
    }
}
using namespace Mashiro;
const int maxn=5e5+10;
int n;
struct point{
    int x,y,v;
}p[maxn];
struct point2{
    int now,hxt;
    double x,y,v,xt;
}p1[maxn];
struct BIT{
    int c[maxn];
    inline int lowbit(int x){
        return x&(~x+1);
    }
    void add(int x,int v=1){
        while(x<=n){
            c[x]+=v;
            x+=lowbit(x);
        }
    }
    int query(int x){
        int res=0;
        while(x){
            res+=c[x];
            x-=lowbit(x);
        }
        return res;
    }
}Tree;
bool cmp(point2 A,point2 B){
    return A.xt<B.xt;
}
int attack[maxn],k,by[maxn];
double bx[maxn];
int Mapy[maxn],Mapx[maxn];
vector<point2>Same[maxn][3];
double Xt[maxn];
int a[maxn];
struct ANS{
    int nowans,sub;
}AA[maxn];
int main() {
    // freopen("missile4.in","r",stdin);
    // freopen("missile4.out","w",stdout);
    read(n,k);
    for(int i(1);i<=n;++i){
        read(p[i].x,p[i].y,p[i].v);
        by[i]=p[i].y;
        double x=p[i].x,y=p[i].y,v=p[i].v;
        double xt=x+v*sqrt(2.0*y/9.8);
        Xt[i]=xt;
        bx[i]=xt;
    }
    for(int i(1);i<=n;++i)read(a[i]);
    sort(bx+1,bx+1+n);
    sort(by+1,by+1+n);
    int my=unique(by+1,by+1+n)-by-1;
    int mx=unique(bx+1,bx+1+n)-bx-1;
    for(int i(1);i<=n;++i){
        double x=p[i].x,y=p[i].y,v=p[i].v;
        int rankx=lower_bound(bx+1,bx+1+mx,Xt[i])-bx;
        int ranky=lower_bound(by+1,by+1+my,p[i].y)-by;
        if(v>0)Same[ranky][0].emplace_back(point2{i,rankx,x,y,v,Xt[i]});
        if(v<0)Same[ranky][1].emplace_back(point2{i,rankx,x,y,v,Xt[i]});
        if(v==0)Same[ranky][2].emplace_back(point2{i,rankx,x,y,v,Xt[i]});
    }
    for(int i(1);i<=my;++i){
        // write(i);
        // putc('\n');
        int nl=Same[i][0].size();
        int nr=Same[i][1].size();
        vector<point2>Temp;

        for(auto j:Same[i][0])Temp.emplace_back(j);
        for(auto j:Same[i][1])Temp.emplace_back(j);
        for(auto j:Same[i][2])Temp.emplace_back(j);
        int nn=Temp.size();
        sort(Temp.begin(),Temp.end(),[](const point2 A,const point2 B){
            return A.x>B.x;
        });
        for(int j(0);j<nn;++j){
            if(Temp[j].v<=0)Tree.add(Temp[j].hxt);
            else {
                int res=Tree.query(Temp[j].hxt);
                attack[Temp[j].now]+=res;
            }
        }
        for(int j(0);j<nn;++j){
            if(Temp[j].v<=0)Tree.add(Temp[j].hxt,-1);
        }
        sort(Temp.begin(),Temp.end(),[](const point2 A,const point2 B){
            return A.x<B.x;
        });
        int cnt=0;
        for(int j(0);j<nn;++j){
            if(Temp[j].v>=0)Tree.add(Temp[j].hxt),++cnt;
            else {
                int res=Tree.query(Temp[j].hxt-1);
                attack[Temp[j].now]+=cnt-res;
            }
        }
        for(int j(0);j<nn;++j){
            if(Temp[j].v>=0)Tree.add(Temp[j].hxt,-1);
        }

        cnt=0;
        for(int j(0);j<nn;++j){
            if(Temp[j].v>0){
                Tree.add(Temp[j].hxt);
                ++cnt;
            }
            else if(Temp[j].v==0){
                int res=Tree.query(Temp[j].hxt-1);
                attack[Temp[j].now]+=cnt-res;
            }
        }
        for(int j(0);j<nn;++j){
            if(Temp[j].v>0){
                Tree.add(Temp[j].hxt,-1);
            }
        }
        sort(Temp.begin(),Temp.end(),[](const point2 A,const point2 B){
            return A.x>B.x;
        });
        for(int j(0);j<nn;++j){
            if(Temp[j].v<0){
                Tree.add(Temp[j].hxt);
            }
            else if(Temp[j].v==0){
                int res=Tree.query(Temp[j].hxt);
                attack[Temp[j].now]+=res;
            }
        }
        for(int j(0);j<nn;++j){
            if(Temp[j].v<0){
                Tree.add(Temp[j].hxt,-1);
            }
        }
        sort(Same[i][0].begin(),Same[i][0].end(),[](const point2 A,const point2 B){
            return A.x<B.x;
        });  
        for(int j(0);j<nl;++j){
            int res=Tree.query(Same[i][0][j].hxt-1);
            attack[Same[i][0][j].now]+=j-res;
            Tree.add(Same[i][0][j].hxt);
        }
        for(int j(0);j<nl;++j){
            Tree.add(Same[i][0][j].hxt,-1);
        }
        sort(Same[i][0].begin(),Same[i][0].end(),[](const point2 A,const point2 B){
            return A.x>B.x;
        });
        for(int j(0);j<nl;++j){
            int res=Tree.query(Same[i][0][j].hxt);
            attack[Same[i][0][j].now]+=res;
            Tree.add(Same[i][0][j].hxt);
        }
        for(int j(0);j<nl;++j){
            Tree.add(Same[i][0][j].hxt,-1);
        }
        sort(Same[i][1].begin(),Same[i][1].end(),[](const point2 A,const point2 B){
            return A.x>B.x;
        });
        for(int j(0);j<nr;++j){
            int res=Tree.query(Same[i][1][j].hxt);
            attack[Same[i][1][j].now]+=res;
            Tree.add(Same[i][1][j].hxt);
        }
        for(int j(0);j<nr;++j){
            Tree.add(Same[i][1][j].hxt,-1);
        }
        sort(Same[i][1].begin(),Same[i][1].end(),[](const point2 A,const point2 B){
            return A.x<B.x;
        });
        for(int j(0);j<nr;++j){
            int res=Tree.query(Same[i][1][j].hxt-1);
            attack[Same[i][1][j].now]+=j-res;
            Tree.add(Same[i][1][j].hxt);
        }
        for(int j(0);j<nr;++j){
            Tree.add(Same[i][1][j].hxt,-1);
        }
    }
    ll ans=0;
    for(int i(1);i<=n;++i){
        AA[i].nowans=attack[i];
        AA[i].sub=a[i];
    }
    sort(AA+1,AA+1+n,[](const ANS A,const ANS B){
        return min(A.nowans,A.sub)>min(B.nowans,B.sub);
    });
    for(int i(1);i<=k;++i){
        ans+=max(0,AA[i].nowans-AA[i].sub);
    }
    for(int i(k+1);i<=n;++i){
        ans+=AA[i].nowans;
    }
    write(ans);
    return 0;
}

回复

13 条回复,欢迎继续交流。

正在加载回复...