QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#200419 | #7523. Partially Free Meal | Diwanul | WA | 110ms | 126904kb | C++14 | 4.1kb | 2023-10-04 16:56:05 | 2023-10-04 16:56:07 |
Judging History
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,LGN=20;
const LL INF=0x3f3f3f3f3f3f3f3f;
//}}}
//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
//}}}
//}}}
//persistent segment tree{{{
int rt[N+10];
struct PST{
int tn;
struct NODE{
int sm,sz,ls,rs;
}nd[N*LGN];
#define LS(u) nd[u].ls
#define RS(u) nd[u].rs
#define SM(u) nd[u].sm
#define SZ(u) nd[u].sz
inline void Modify(int old,int &u,int l,int r,int x,int y){
u=++tn;
SM(u)=SM(old)+y;
SZ(u)=SZ(old)+1;
if(l==r)
return;
int mid=(l+r)>>1;
if(x>mid)
Modify(RS(old),RS(u),mid+1,r,x,y);
else
Modify(LS(old),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)));
}
}pt;
//}}}
//solve{{{
int st[N+10],tst;
inline int Calc(int x,int y){
return y>x?INF:pt.Query(rt[x-1],1,n,y-1)+lsh[a[x].a]+a[x].b;
}
inline bool Check(int x,int y,int z){
return 0;
int l=1,r=z-1,ans=z;
while(l<=r){
int mid=(l+r)>>1;
if(Calc(z,mid)<=Calc(y,mid))
r=(ans=mid)-1;
else
l=mid+1;
}
if(y==118&&Calc(x,ans)<=Calc(z,ans))
printf("%lld %lld %lld %lld %lld %lld %lld\n",x,y,z,ans,Calc(x,ans),Calc(y,ans),Calc(z,ans));
return Calc(x,ans)<=Calc(z,ans);
}
//}}}
//main{{{
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)
pt.Modify(rt[i-1],rt[i],1,tl,a[i].a,lsh[a[i].a]);
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>1&&Check(st[tst-1],st[tst],i)))
--tst;
st[++tst]=i;
}
for(int i=1,j=1;i<=tst&&j<=n;++i){
int di=st[i],ni=st[i+1];
/*
if(n==200000){
printf("%lld %lld\n",di,ni);
printf("%lld %lld %lld\n",j,lsh[a[di].a],a[di].b);
if(di==873)
for(int t=1;t<=5;++t)
printf("s%lld\n",sgt1.Query(1,1,n,t)-sgt1.Query(1,1,n,t-1));
}
*/
while(j<=di&&(di==n||Calc(di,j)<Calc(ni,j)))
printf("%lld\n",Calc(di,j)),++j;
}
return 0;
}
//}}}
//《象》曰:泽灭木,大过。君子以独立不惧,遁世无闷。
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 5576kb
input:
3 2 5 4 3 3 7
output:
7 11 16
result:
ok 3 lines
Test #2:
score: -100
Wrong Answer
time: 110ms
memory: 126904kb
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 126446521 1126443579 2126440637 3126437695 4126434753 5126431811 6126428869 7126425927 8126422985 9126420043 10126417101 11126414159 12126411217 13126408275 14126405333 15126402391 16126399449 17126396507 18126393565 19126390623 20126387681 21126384739 22126381797 23126378855 24126375913 251...
result:
wrong answer 2nd lines differ - expected: '3208018', found: '126446521'