QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#276844 | #7517. Flying Ship Story | ship2077 | ML | 0ms | 0kb | C++14 | 1.7kb | 2023-12-06 11:36:43 | 2023-12-06 11:36:44 |
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
constexpr int M=2e5+5;LL ans[M];
int n,m,num,rt[M],lsh[M];struct node{int x,y;}a[M];
struct SegTree{int ls,rs,siz;LL sum;}tr[M*80];
int read(){
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)) x=x*10+ch-48,ch=getchar();
return x*f;
}
int new_node(int x){tr[++num]=tr[x];return num;}
void update(int now,int u,int l=1,int r=m){
tr[now].siz++;tr[now].sum+=lsh[u];
if (l==r) return ; int mid=l+r>>1;
if (u<=mid) update(tr[now].ls=new_node(tr[now].ls),u,l,mid);
else update(tr[now].rs=new_node(tr[now].rs),u,mid+1,r);
}
LL query(int now,int k,int l=1,int r=m){
if (!now) return 0;
if (l==r) return 1ll*lsh[l]*k;
int mid=l+r>>1,siz=tr[tr[now].ls].siz;
if (k<=siz) return query(tr[now].ls,k,l,mid);
return tr[tr[now].ls].sum+query(tr[now].rs,k-siz,mid+1,r);
}
LL getans(int x,int k){return query(rt[x],k)+a[x].y;}
void solve(int ql,int qr,int xl,int xr){
if (ql>qr) return ;
if (xl==xr){
for (int i=ql;i<=qr;i++)
ans[i]=getans(xl,i);
return ;
}
int mid=ql+qr>>1,pos=0;
for (int i=max(mid,xl);i<=xr;i++){
const LL tmp=getans(i,mid);
if (tmp<ans[mid]) ans[mid]=tmp,pos=i;
}
solve(ql,mid-1,xl,pos);solve(mid+1,qr,pos,xr);
}
int main(){ n=read();
for (int i=1;i<=n;i++) a[i]={read(),read()},lsh[i]=a[i].x;
sort(a+1,a+n+1,[](node a,node b){return a.y<b.y;});
sort(lsh+1,lsh+n+1);m=unique(lsh+1,lsh+n+1)-lsh-1;
for (int i=1;i<=n;i++) a[i].x=lower_bound(lsh+1,lsh+n+1,a[i].x)-lsh;
for (int i=1;i<=n;i++) update(rt[i]=new_node(rt[i-1]),a[i].x);
memset(ans,0x3f,sizeof(ans)); solve(1,n,1,n);
for (int i=1;i<=n;i++) printf("%lld\n",ans[i]);
return 0;
}
詳細信息
Test #1:
score: 0
Memory Limit Exceeded
input:
5 1 2 3 1 1 4 5 2 2 2 2 2 3 7 2 3 4
output:
3 5 8 11 16