QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#200008#7523. Partially Free Mealucup-team1479#WA 148ms25820kbC++143.4kb2023-10-04 15:04:012023-10-04 15:04:02

Judging History

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

  • [2023-10-04 15:04:02]
  • 评测
  • 测评结果:WA
  • 用时:148ms
  • 内存:25820kb
  • [2023-10-04 15:04:01]
  • 提交

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;
//}}}

//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
//}}}
//}}}

//segment tree{{{
struct SGT{
	struct NODE{
		int sm,sz;
	}nd[N<<2];

#define LS(u) (u<<1)
#define RS(u) ((u<<1)|1)
#define SM(u) nd[u].sm
#define SZ(u) nd[u].sz

	inline void Modify(int u,int l,int r,int x,int y){
		SM(u)+=y;
		++SZ(u);
		if(l==r)
			return;
		int mid=(l+r)>>1;
		if(x>mid)
			Modify(RS(u),mid+1,r,x,y);
		else
			Modify(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)));
	}
}sgt1,sgt2;
//}}}

//main{{{
signed main(){
#ifdef FILE
	freopen(".in","r",stdin);
	freopen(".out","w",stdout);
#endif
	n=Read();
	int st=1;
	for(int i=1;i<=n;++i){
		a[i].Init();
		if(a[i].a+a[i].b<a[st].a+a[st].b)
			st=i;
	}
	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);
	sgt2.Modify(1,1,tl,a[1].a,lsh[a[1].a]);
	for(int i=2;i<st;++i)
		sgt1.Modify(1,1,tl,a[i-1].a,lsh[a[i-1].a]),sgt2.Modify(1,1,tl,a[i].a,lsh[a[i].a]);
	for(int i=st,j=1;i<=n&&j<=n;++i){
		if(i>1)
			sgt1.Modify(1,1,tl,a[i-1].a,lsh[a[i-1].a]);
		sgt2.Modify(1,1,tl,a[i].a,lsh[a[i].a]);
		while(j<=i&&(i==n||sgt1.Query(1,1,n,j-1)+lsh[a[i].a]+a[i].b<sgt2.Query(1,1,n,j-1)+lsh[a[i+1].a]+a[i+1].b))
			printf("%lld\n",sgt1.Query(1,1,n,j-1)+lsh[a[i].a]+a[i].b),++j;
	}
	return 0;
}
//}}}
//《象》曰:泽灭木,大过。君子以独立不惧,遁世无闷。

詳細信息

Test #1:

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

input:

3
2 5
4 3
3 7

output:

7
11
16

result:

ok 3 lines

Test #2:

score: -100
Wrong Answer
time: 148ms
memory: 25820kb

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:

515093036
515096410
515100630
515109317
515121843
515139069
515158650
515182050
515209304
515256387
515307274
515380718
515468818
515561978
515657773
515759650
515870813
515992885
516121609
516271550
516427168
516589513
516753464
516932085
517126080
517326381
517527251
517737059
517954314
518196385
...

result:

wrong answer 1st lines differ - expected: '1318594', found: '515093036'