社区讨论
有码量少的写法吗?
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 条回复,欢迎继续交流。
正在加载回复...