QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#200135#7523. Partially Free Mealucup-team1479#WA 123ms26308kbC++143.7kb2023-10-04 15:29:522023-10-04 15:29:52

Judging History

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

  • [2023-10-04 15:29:52]
  • 评测
  • 测评结果:WA
  • 用时:123ms
  • 内存:26308kb
  • [2023-10-04 15:29:52]
  • 提交

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

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

詳細信息

Test #1:

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

input:

3
2 5
4 3
3 7

output:

7
11
16

result:

ok 3 lines

Test #2:

score: -100
Wrong Answer
time: 123ms
memory: 26308kb

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
11487338
12898863
14697855
14788280
16172895
17768627
19336633
20693779
22005236
23389851
25073157
26760338
28509336
30294967
32093959
33976461
35893858
37754030
39588384
41470886
43388283
45309771
47573762
49838235
52476909
55158583
58072674
61026526
64003437...

result:

wrong answer 6th lines differ - expected: '11149865', found: '11487338'