QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#276844#7517. Flying Ship Storyship2077ML 0ms0kbC++141.7kb2023-12-06 11:36:432023-12-06 11:36:44

Judging History

你现在查看的是最新测评结果

  • [2023-12-06 11:36:44]
  • 评测
  • 测评结果:ML
  • 用时:0ms
  • 内存:0kb
  • [2023-12-06 11:36:43]
  • 提交

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

result: