QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#200419#7523. Partially Free MealDiwanulWA 110ms126904kbC++144.1kb2023-10-04 16:56:052023-10-04 16:56:07

Judging History

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

  • [2023-10-04 16:56:07]
  • 评测
  • 测评结果:WA
  • 用时:110ms
  • 内存:126904kb
  • [2023-10-04 16:56:05]
  • 提交

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);
		else
			Modify(LS(old),LS(u),l,mid,x,y);
	}

	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{{{
int st[N+10],tst;

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 bool Check(int x,int y,int z){
	return 0;
	int l=1,r=z-1,ans=z;
	while(l<=r){
		int mid=(l+r)>>1;
		if(Calc(z,mid)<=Calc(y,mid))
			r=(ans=mid)-1;
		else
			l=mid+1;
	}
	if(y==118&&Calc(x,ans)<=Calc(z,ans))
		printf("%lld %lld %lld %lld %lld %lld %lld\n",x,y,z,ans,Calc(x,ans),Calc(y,ans),Calc(z,ans));
	return Calc(x,ans)<=Calc(z,ans);
}
//}}}

//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]);
	for(int i=1;i<=n;++i){
		while((tst&&lsh[a[st[tst]].a]+a[st[tst]].b>lsh[a[i].a]+a[i].b)||(tst>1&&Check(st[tst-1],st[tst],i)))
			--tst;
		st[++tst]=i;
	}
	for(int i=1,j=1;i<=tst&&j<=n;++i){
		int di=st[i],ni=st[i+1];
		/*
		if(n==200000){
			printf("%lld %lld\n",di,ni);
			printf("%lld %lld %lld\n",j,lsh[a[di].a],a[di].b);
			if(di==873)
				for(int t=1;t<=5;++t)
					printf("s%lld\n",sgt1.Query(1,1,n,t)-sgt1.Query(1,1,n,t-1));
		}
		*/
		while(j<=di&&(di==n||Calc(di,j)<Calc(ni,j)))
			printf("%lld\n",Calc(di,j)),++j;
	}
	return 0;
}
//}}}
//《象》曰:泽灭木,大过。君子以独立不惧,遁世无闷。

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 5576kb

input:

3
2 5
4 3
3 7

output:

7
11
16

result:

ok 3 lines

Test #2:

score: -100
Wrong Answer
time: 110ms
memory: 126904kb

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
126446521
1126443579
2126440637
3126437695
4126434753
5126431811
6126428869
7126425927
8126422985
9126420043
10126417101
11126414159
12126411217
13126408275
14126405333
15126402391
16126399449
17126396507
18126393565
19126390623
20126387681
21126384739
22126381797
23126378855
24126375913
251...

result:

wrong answer 2nd lines differ - expected: '3208018', found: '126446521'