QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#866904 | #9222. Price Combo | lyx123886a123886 | WA | 223ms | 70312kb | C++14 | 4.4kb | 2025-01-22 21:34:20 | 2025-01-22 21:34:21 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dec(i,a,b) for(int i=(a);i>=(b);--i)
using ll=long long;
using pi=pair<int,int>;
using vi=vector<int>;
using vp=vector<pi>;
template<class T> bool chkmin(T &x,T y) {return (y<x)?(x=y,true):false;}
template<class T> bool chkmax(T &x,T y) {return (y>x)?(x=y,true):false;}
#define pb push_back
#define SZ(x) int(x.size())
#define fi first
#define se second
#define LOCAL 0
#define open_file if(LOCAL) {freopen("a.in","r",stdin);freopen("a.out","w",stdout);}
int read() {int x;scanf("%d",&x);return x;}
using info=array<array<ll,2>,2>;
void operator +=(info &x,const info &y) {
rep(i,0,1) rep(j,0,1) chkmin(x[i][j],y[i][j]);
}
info operator +(info x,const info &y) {
x+=y;return x;
}
ll getmin(const info &x) {return min(min(x[0][0],x[0][1]),min(x[1][0],x[1][1]));}
using tag=array<ll,3>;//(for 0,for 1,ou/ji)
void operator +=(tag &x,const tag &y) {
ll &op=x[2];
x[0]+=y[op],x[1]+=y[op^1],op^=y[2];
}
tag operator +(tag x,const tag &y) {
x+=y;return x;
}
void operator *=(info &x,const tag &y) {//only change the second
x[0][0]+=y[0],x[1][0]+=y[0];
x[0][1]+=y[1],x[1][1]+=y[1];
if(y[2]) swap(x[0][0],x[0][1]),swap(x[1][0],x[1][1]);
}
info operator *(info x,const tag &y) {
x*=y;return x;
}
int n;
const ll inf=1e18;
const int MAXN=2e5+50;
namespace sgt {
#define ls (k<<1)
#define rs (k<<1|1)
struct node {
info pref;tag who;
const node operator +(const node &rg) const {
return (node){pref+rg.pref*who,rg.who+who};
}
} s[MAXN<<2];
tag tg[MAXN<<2];//first //only change the first
bool has[MAXN<<2];
void init() {
rep(k,1,(n+1)<<2) {
for(int o:{0,1}) s[k].pref[o].fill(inf);
s[k].pref[0][0]=0;//!
s[k].who={0,0,0};
tg[k]={0,0,0};
has[k]=false;
}
}
void upd(int k) {
s[k]=s[ls]+s[rs];
}
void apply(int k,const tag &t) {//first
has[k]=true;
auto &x=s[k].pref;
x[0][0]+=t[0],x[0][1]+=t[0];
x[1][0]+=t[1],x[1][1]+=t[1];
if(t[2]) swap(x[0],x[1]);
tg[k]+=t;
}
void push_down(int k) {
if(has[k])
apply(ls,tg[k]),apply(rs,tg[k]),tg[k].fill(0),has[k]=false;
}
void Chkpos(int k,int l,int r,int pos,const info &f) {
if(l==r) {s[k].pref=f*s[k].who;return ;}
push_down(k);int mid=l+r>>1;
if(pos<=mid) Chkpos(ls,l,mid,pos,f);
else Chkpos(rs,mid+1,r,pos,f);
return upd(k);
}
void Inssec(int k,int l,int r,int pos,int val) {
if(l==r) {
s[k].who={val,0,1};//!!
s[k].pref*=s[k].who;
return ;
}
push_down(k);int mid=l+r>>1;
if(pos<=mid) Inssec(ls,l,mid,pos,val);
else Inssec(rs,mid+1,r,pos,val);
return upd(k);
}
void Modify(int k,int l,int r,int x,int y,int val) {
if(l>=x&&r<=y) return apply(k,{val,0,1});
push_down(k);int mid=l+r>>1;
if(x<=mid) Modify(ls,l,mid,x,y,val);
if(y>=mid+1) Modify(rs,mid+1,r,x,y,val);
return upd(k);
}
node Query(int k,int l,int r,int x,int y) {
if(l>=x&&r<=y) return s[k];
push_down(k);int mid=l+r>>1;
if(y<=mid) return Query(ls,l,mid,x,y);
if(x>=mid+1) return Query(rs,mid+1,r,x,y);
return Query(ls,l,mid,x,y)+Query(rs,mid+1,r,x,y);
}
void chk(int pos,const info &f) {
Chkpos(1,1,n+1,pos,f);
}
void ins(int pos,int val) {
Inssec(1,1,n+1,pos,val);
}
void mdf(int l,int r,int val) {
Modify(1,1,n+1,l,r,val);
}
info qry(int l,int r) {
return Query(1,1,n+1,l,r).pref;
}
#undef ls
#undef rs
};
pi a[MAXN];
int sa[MAXN],rk[MAXN];
void solve() {
n=read();
rep(i,1,n) a[i].fi=read();
rep(i,1,n) a[i].se=read();
sort(a+1,a+1+n);
rep(i,1,n) sa[i]=i;sort(sa+1,sa+1+n,[&](auto i,auto j){return a[i].se<a[j].se;});
rep(i,1,n) rk[sa[i]]=i;
sgt::init();
dec(id,n,1) {
int pos=rk[id];
int nxt=(id>1)?rk[id-1]:1;
sgt::mdf(1,pos,a[id].fi);
sgt::ins(pos+1,a[id].se);
sgt::chk(nxt,sgt::qry(nxt+1,n+1));
}
ll ans=getmin(sgt::qry(1,1));
printf("%lld",ans);
}
int main() {
open_file
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 10064kb
input:
7 10 12 19 99 10 8 49 9 14 15 199 11 7 19
output:
131
result:
ok single line: '131'
Test #2:
score: 0
Accepted
time: 0ms
memory: 10068kb
input:
7 10 12 19 99 10 8 49 9 14 15 199 11 7 19
output:
131
result:
ok single line: '131'
Test #3:
score: 0
Accepted
time: 223ms
memory: 70296kb
input:
199913 1212731 2525164 3210261 2457211 1013738 1931420 923123 867112 762069 2108660 108920 2491869 867107 387025 2278045 574027 1661570 820133 1274150 2001346 779766 3305537 3000211 2418643 2108660 2001343 1074820 2754411 826712 3117447 1661569 338161 1849064 3007920 3057426 468078 3252798 1274146 4...
output:
154816494865
result:
ok single line: '154816494865'
Test #4:
score: 0
Accepted
time: 194ms
memory: 70304kb
input:
200000 97216869 743886950 33071099 93740214 165915739 714765240 770423425 498199793 631193672 753722174 569396548 842251035 911607641 450531347 765200530 739362614 91640365 174209387 248940417 335559443 238573490 479206903 882783448 200485674 717481029 526848873 692757023 616376164 573933118 2566387...
output:
49954742111708
result:
ok single line: '49954742111708'
Test #5:
score: 0
Accepted
time: 198ms
memory: 70248kb
input:
200000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000...
output:
100000000000000
result:
ok single line: '100000000000000'
Test #6:
score: -100
Wrong Answer
time: 193ms
memory: 70312kb
input:
200000 274771488 823198191 332419028 866914185 137030479 445861162 505221814 805396419 842179806 540452002 510333908 765762441 345734318 975440944 186438657 676989478 108190396 339715111 337119327 462480232 634226928 438891079 609658471 156142766 16523966 699505629 190085420 960768051 824783291 5029...
output:
49967269431863
result:
wrong answer 1st lines differ - expected: '49967269431852', found: '49967269431863'