QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#200184 | #7523. Partially Free Meal | OccDreamer | WA | 2ms | 11824kb | C++14 | 3.2kb | 2023-10-04 15:41:31 | 2023-10-04 15:41:31 |
Judging History
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'