QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#200184#7523. Partially Free MealOccDreamerWA 2ms11824kbC++143.2kb2023-10-04 15:41:312023-10-04 15:41:31

Judging History

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

  • [2023-10-04 15:41:31]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:11824kb
  • [2023-10-04 15:41:31]
  • 提交

answer

//code by Emissary
#include<bits/stdc++.h>

#define fi first
#define se second
#define vc vector
#define db double
#define ll long long
#define mk make_pair
#define pb push_back
#define PI pair<int,int>
#define ull unsigned long long
#define err cerr << "   -_-   " << endl
#define debug cerr << " ------------------- " << endl

#define input(x) freopen(#x".in","r",stdin)
#define output(x) freopen(#x".out","w",stdout)

#define NO puts("No")
#define YES puts("Yes")

#define int long long

using namespace std;

namespace IO{
	inline int read(){
		int X=0, W=0; char ch=getchar();
		while(!isdigit(ch)) W|=ch=='-', ch=getchar();
		while(isdigit(ch)) X=(X<<1)+(X<<3)+(ch^48), ch=getchar();
		return W?-X:X;
	}
	inline void write(ll x){
		if(x<0) x=-x, putchar('-');
		if(x>9) write(x/10);
		putchar(x%10+'0');
	}
	inline void sprint(ll x){write(x), putchar(32);}
	inline void eprint(ll x){write(x), putchar(10);}
}using namespace IO;

const int inf = 2e9;
const int MAXN = 2e5+5;

ll res[MAXN], ans, sum[MAXN*40];

int tot, Pos[MAXN];
int n, le[MAXN], ri[MAXN];
int root[MAXN], lc[MAXN*40], rc[MAXN*40], tree[MAXN*40];

bool mark[MAXN];

struct IT{
	int x, y;
	inline bool friend operator < (const IT &x, const IT &y){
		return x.y==y.y?x.x<y.x:x.y<y.y;
	}
}a[MAXN];

inline void build(int &now, int pre, int l, int r, int pos){
	now=++tot; lc[now]=lc[pre]; rc[now]=rc[pre];
	tree[now]=tree[pre]+1; sum[now]=sum[pre]+pos;
	if(l==r) return ;
	int mid=(l+r)>>1;
	if(pos<=mid) build(lc[now],lc[pre],l,mid,pos);
	else build(rc[now],rc[pre],mid+1,r,pos);
	return ;
}

int rk, ing[MAXN];

inline void ask(int now, int l, int r){
	if(tree[now]<=rk){
		rk-=tree[now];
		ans+=sum[now];
		return ;
	}
	if(l==r){
		if(rk>=tree[now]) rk-=tree[now], ans+=1ll*tree[now]*l;
		else ans+=1ll*rk*l, rk=0;
		return ;
	}
	if(rk==0) return ;
	int mid=(l+r)>>1;
	ask(lc[now],l,mid); ask(rc[now],mid+1,r);
	return ;
}

inline int Qsum(int now, int l, int r, int L, int R){
	if(L<=l && r<=R) return tree[now];
	int mid=(l+r)>>1, res=0;
	if(L<=mid) res+=Qsum(lc[now],l,mid,L,R);
	if(R>mid) res+=Qsum(rc[now],mid+1,r,L,R);
	return res;
}

int stk[MAXN], topf;

signed main(){
	n=read(); set<int> S;
	for(int i=1;i<=n;++i) res[i]=1e18;
	for(int i=1;i<=n;++i) S.insert(i), a[i].x=read(), a[i].y=read();
	sort(a+1,a+1+n); ll g;
	for(int i=n;i>=1;--i){
		while(topf && a[stk[topf]].x+a[stk[topf]].y<a[i].x+a[i].y) --topf;
		stk[++topf]=i;
	}
	while(topf) mark[stk[topf]]=1, --topf;
	for(int i=1;i<=n;++i) g=min(a[i].x+a[i].y,g), build(root[i],root[i-1],1,inf,a[i].x);
	for(int i=1;i<=n;++i){
		if(a[i].x+a[i].y>a[i-1].x+a[i-1].y) continue;
		int u=Qsum(root[i],1,inf,1,a[i].x+a[i].y-a[i-1].y);
		ri[i]=i; le[i]=u;
		for(int j=u;j<=min(53ll,i);++j){
			rk=j; ans=0; ask(root[i],1,inf); res[j]=min(res[j],ans+a[i].y);
			if(res[j]==ans+a[i].y) Pos[j]=i;
		}
		for(int j=1;j<min(53ll,u);++j) if(!ing[j] && Pos[j]) ing[j]=i;
	}
	if(n<=3){
		for(int i=1;i<=n;++i) eprint(res[i]);
		return 0;
	}	
	for(int i=1;i<=n;++i) sprint(res[i]), sprint(Pos[i]), eprint(ing[i]);
	return 0;
}





































































詳細信息

Test #1:

score: 0
Wrong Answer
time: 2ms
memory: 11824kb

input:

3
2 5
4 3
3 7

output:

1000000000000000000
11
1000000000000000000

result:

wrong answer 1st lines differ - expected: '7', found: '1000000000000000000'