QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#200492#7523. Partially Free MealDiwanulWA 472ms127052kbC++143.6kb2023-10-04 17:10:062023-10-04 17:10:06

Judging History

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

  • [2023-10-04 17:10:06]
  • 评测
  • 测评结果:WA
  • 用时:472ms
  • 内存:127052kb
  • [2023-10-04 17:10:06]
  • 提交

answer

//prepare for coding{{{
//preparaton{{{
#include<bits/stdc++.h>

//#define RELEASE
#ifdef RELEASE
#define DB(...) ;
#else
//#define FILE
#ifdef FILE
#define DB(...) fprintf(stderr,__VA_ARGS__)
#else
#define DB printf
#endif
#endif 
//#define MOD_OPERATOR
//#define CMP_OPERATOR
//#define GRP_OPERATOR
#define int LL
//}}}

//constants{{{
typedef long long LL;

const int N=200000,LGN=20;
const LL INF=0x3f3f3f3f3f3f3f3f;
//}}}

//std{{{
using namespace std;
//}}}

//input and output{{{
inline int Read(){
	char c=getchar();
	int res=0;
	bool b=0;
	while(c>'9'||c<'0')
		b=(c=='-'),c=getchar();
	while(c>='0'&&c<='9')
		res=(res<<3)+(res<<1)+c-'0',c=getchar();
	return b?-res:res;
}
//}}}

//other small functions{{{
//}}}

//variables{{{
int n;
int lsh[N+10],tl;

struct ITEM{
	int a,b;

	inline bool operator<(const ITEM &x)const{
		return b<x.b;
	}

	inline void Init(){
		lsh[++tl]=a=Read();
		b=Read();
	}
}a[N+10];
//}}}

//modulo operators{{{
#ifdef MOD_OPERATOR
const int MOD=998244353;

inline int Add(int a,int b){
	return a+b<MOD?a+b:a+b-MOD;
}

inline int MAdd(int &x,int y){
	return (x+=y)<MOD?x:x-=MOD;
}

inline int Mul(int a,int b){
	return 1ll*a*b%MOD;
}

inline int MMul(int &x,int y){
	return x=1ll*x*y%MOD;
}

inline int Pow(int x,int b=MOD-2){
	int res=1;
	while(b){
		if(b&1)
			MMul(res,x);
		MMul(x,x);
		b>>=1;
	}
	return res;
}
#endif
//}}}

//compare operators{{{
inline int Max(int a,int b){
	return a<b?b:a;
}

inline int CMX(int &x,int y){
	return x<y?x=y:x;
}

inline int Min(int a,int b){
	return a>b?b:a;
}

inline int CMN(int &x,int y){
	return x>y?x=y:x;
}
//}}}

//graph operators{{{
#ifdef GRP_OPERATOR
int te=1,head[N+10];
int s,t;

struct EDGE{
	int n,t;
}e[N*2+10];

inline void Adde(int u,int v){
	e[++te].n=head[u];
	e[te].t=v;
	head[u]=te;
	e[++te].n=head[v];
	e[te].t=u;
	head[v]=te;
}
#endif
//}}}
//}}}

//persistent segment tree{{{
int rt[N+10];

struct PST{
	int tn;

	struct NODE{
		int sm,sz,ls,rs;
	}nd[N*LGN];

#define LS(u) nd[u].ls
#define RS(u) nd[u].rs
#define SM(u) nd[u].sm
#define SZ(u) nd[u].sz

	inline void Modify(int old,int &u,int l,int r,int x,int y){
		u=++tn;
		SM(u)=SM(old)+y;
		SZ(u)=SZ(old)+1;
		if(l==r)
			return;
		int mid=(l+r)>>1;
		if(x>mid)
			Modify(RS(old),RS(u),mid+1,r,x,y),LS(u)=LS(old);
		else
			Modify(LS(old),LS(u),l,mid,x,y),RS(u)=RS(old);
	}

	inline int Query(int u,int l,int r,int x){
		if(l==r)
			return x*lsh[l];
		int mid=(l+r)>>1;
		if(x<SZ(LS(u)))
			return Query(LS(u),l,mid,x);
		else
			return SM(LS(u))+Query(RS(u),mid+1,r,x-SZ(LS(u)));
	}
}pt;
//}}}

//solve{{{
inline int Calc(int x,int y){
	return y>x?INF:pt.Query(rt[x-1],1,n,y-1)+lsh[a[x].a]+a[x].b;
}

inline void Solve(int l,int r,int sl,int sr){
	if(l>r)
		return;
	if(sl==sr){
		for(int i=l;i<=r;++i)
			printf("%lld\n",Calc(sl,i));
		return;
	}
	int mid=(l+r)>>1;
	int wm=sl;
	for(int i=sl+1;i<=sr;++i)
		if(Calc(i,mid)<Calc(wm,mid))
			wm=i;
	Solve(l,mid-1,sl,wm);
	printf("%lld\n",Calc(wm,mid));
	Solve(mid+1,r,wm,sr);
}
//}}}

//main{{{
signed main(){
#ifdef FILE
	freopen(".in","r",stdin);
	freopen(".out","w",stdout);
#endif
	n=Read();
	for(int i=1;i<=n;++i)
		a[i].Init();
	sort(lsh+1,lsh+1+tl);
	tl=unique(lsh+1,lsh+1+tl)-lsh-1;
	for(int i=1;i<=n;++i)
		a[i].a=lower_bound(lsh+1,lsh+1+tl,a[i].a)-lsh;
	sort(a+1,a+1+n);
	for(int i=1;i<=n;++i)
		pt.Modify(rt[i-1],rt[i],1,tl,a[i].a,lsh[a[i].a]);
	Solve(1,n,1,n);
	return 0;
}
//}}}
//《象》曰:泽灭木,大过。君子以独立不惧,遁世无闷。

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 5880kb

input:

3
2 5
4 3
3 7

output:

7
11
16

result:

ok 3 lines

Test #2:

score: -100
Wrong Answer
time: 472ms
memory: 127052kb

input:

200000
466436993 804989151
660995237 756645598
432103296 703610564
6889895 53276988
873617076 822481192
532911431 126844295
623111499 456772252
937464699 762157133
708503076 786039753
78556972 5436013
582960979 398984169
786333369 325119902
930705057 615928139
924915828 506145001
164984329 208212435...

output:

1318594
3208018
5570526
7340845
9223347
11149865
12332210
13476823
14788280
16172895
17768627
19336633
20693779
22005236
23389851
25073157
26760338
28509336
30294967
32093959
33976461
35893858
37754030
39588384
41470886
43388283
45309771
47309654
48837539
50417767
52079411
53762717
55190044
56577630...

result:

wrong answer 56937th lines differ - expected: '5504165214647', found: '5504165217805'