QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#236904 | #7523. Partially Free Meal | by_chance | WA | 274ms | 96800kb | C++14 | 1.8kb | 2023-11-04 11:27:37 | 2023-11-04 11:27:37 |
Judging History
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'