QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#236904#7523. Partially Free Mealby_chanceWA 274ms96800kbC++141.8kb2023-11-04 11:27:372023-11-04 11:27:37

Judging History

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

  • [2023-11-04 11:27:37]
  • 评测
  • 测评结果:WA
  • 用时:274ms
  • 内存:96800kb
  • [2023-11-04 11:27:37]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
int n,m;ll y[N],ans[N];
int ls[N<<5],rs[N<<5],cnt[N<<5],tot;ll sum[N<<5];
struct node{ll a,b;}x[N];
bool operator <(const node&a,const node&b){return a.b<b.b;}
#define mid ((l+r)>>1)
int build(int l,int r){
    int p=++tot;if(l==r)return p;
    ls[p]=build(l,mid);rs[p]=build(mid+1,r);return p;
}
int modify(int q,int l,int r,int x){
    int p=++tot;ls[p]=ls[q];rs[p]=rs[q];cnt[p]=cnt[q];sum[p]=sum[q];
    if(l==r){++cnt[p];sum[p]+=y[x];return p;}
    if(x<=mid)ls[p]=modify(ls[q],l,mid,x);
    else rs[p]=modify(rs[q],mid+1,r,x);
    cnt[p]=cnt[ls[p]]+cnt[rs[p]];
    sum[p]=sum[ls[p]]+sum[rs[p]];
    return p;
}
ll query(int p,int l,int r,int x){
    if(l==r)return x*y[l];
    if(cnt[ls[p]]>x)return query(ls[p],l,mid,x);
    return query(rs[p],mid+1,r,x-cnt[ls[p]])+sum[ls[p]];
}
#undef mid
int root[N];
ll query(int i,int k){
    if(i<k)return 1e18;
    return query(root[i],1,m,k);
}
void solve(int l,int r,int pl,int pr){
    if(l>r)return;
    if(pl==pr){
        for(int i=l;i<=r;i++)
            ans[i]=x[pl].b+query(pl,i);
        return;
    }
    ll res=1e18,pos=pl;
    int mid=l+r>>1;
    for(int i=pl;i<=pr;i++){
        ll val=x[i].b+query(i,mid);
        if(val<res)res=val,pos=i;
    }
    ans[mid]=res;
    solve(l,mid-1,pl,pos);
    solve(r,mid+1,pos,pr);
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld%lld",&x[i].a,&x[i].b),y[i]=x[i].a;
    sort(x+1,x+n+1);
    sort(y+1,y+n+1);m=unique(y+1,y+n+1)-y-1;
    root[0]=build(1,m);
    for(int i=1;i<=n;i++)
        root[i]=modify(root[i-1],1,m,lower_bound(y+1,y+m+1,x[i].a)-y);
    solve(1,n,1,n);
    for(int i=1;i<=n;i++)
        printf("%lld\n",ans[i]);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3
2 5
4 3
3 7

output:

7
11
16

result:

ok 3 lines

Test #2:

score: -100
Wrong Answer
time: 274ms
memory: 96800kb

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
7834517
0
11149865
0
0
0
0
0
19336633
0
0
0
0
0
0
0
0
0
0
0
39588384
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
79759027
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
163741214
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

wrong answer 4th lines differ - expected: '7340845', found: '7834517'