QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#866796 | #9222. Price Combo | lyx123886a123886 | WA | 184ms | 70328kb | C++14 | 4.4kb | 2025-01-22 19:04:25 | 2025-01-22 19:04:25 |
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];
}
int n;
const int MAXN=2e5+50;
namespace sgt {
const ll inf=1e18;
#define ls (k<<1)
#define rs (k<<1|1)
info s[MAXN<<2];
tag tg1[MAXN<<2],tg2[MAXN<<2];
bool has[MAXN<<2];
void upd(int k) {s[k]=s[ls]+s[rs];}
void apply1(int k,const tag &t) {
has[k]=true;
s[k][0][0]+=t[0],s[k][0][1]+=t[0];
s[k][1][0]+=t[1],s[k][1][1]+=t[1];
if(t[2]) swap(s[k][0],s[k][1]);
tg1[k]+=t;
}
void apply2(int k,const tag &t) {
has[k]=true;
s[k][0][0]+=t[0],s[k][1][0]+=t[0];
s[k][0][1]+=t[1],s[k][1][1]+=t[1];
if(t[2]) swap(s[k][0][0],s[k][0][1]),swap(s[k][1][0],s[k][1][1]);
tg2[k]+=t;
}
void push_down(int k) {
if(!has[k]) return ;
apply1(ls,tg1[k]),apply2(ls,tg2[k]);
apply1(rs,tg1[k]),apply2(rs,tg2[k]);
tg1[k].fill(0);tg2[k].fill(0);
has[k]=false;
}
void Ins(int k,int l,int r,int pos,const info &f) {
if(l==r) {s[k]+=f;return ;}
push_down(k);int mid=l+r>>1;
if(pos<=mid) Ins(ls,l,mid,pos,f);
else Ins(rs,mid+1,r,pos,f);
return upd(k);
}
info 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 Modify(int k,int l,int r,int x,int y,int val,int op) {
if(l>=x&&r<=y) return (op==1)?apply1(k,{val,0,1}):apply2(k,{val,0,1});
push_down(k);int mid=l+r>>1;
if(x<=mid) Modify(ls,l,mid,x,y,val,op);
if(y>=mid+1) Modify(rs,mid+1,r,x,y,val,op);
return upd(k);
}
void ins(int pos,const info &f) {
Ins(1,1,n+1,pos,f);
}
void mdf1(int l,int r,int val) {
Modify(1,1,n+1,l,r,val,1);
}
void mdf2(int l,int r,int val) {
Modify(1,1,n+1,l,r,val,2);
}
info qry(int l,int r) {
return Query(1,1,n+1,l,r);
}
void init() {
rep(k,1,(n+1)<<2) {
s[k][0].fill(inf),s[k][1].fill(inf);
s[k][0][0]=0;
has[k]=false;
tg1[k].fill(0),tg2[k].fill(0);
}
}
#undef ls
#undef rs
};
// info dp[MAXN];
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 lval=a[id].se,rval=a[id].fi;
sgt::ins(pos,sgt::qry(pos+1,n+1));
sgt::mdf2(1,pos,lval);
sgt::mdf1(pos+1,n+1,rval);
}
ll ans=getmin(sgt::qry(1,n+1));
printf("%lld",ans);
// memset(dp,60,sizeof(dp));
// rep(i,1,n+1) dp[i][0][0]=0;
// dec(id,n,1) {
// int pos=rk[id];
// int lval=a[id].se,rval=a[id].fi;
// //left::sec right:fir
// rep(i,pos+1,n+1) dp[pos]+=dp[i];
// rep(i,1,pos) add2(dp[i],lval);
// rep(i,pos+1,n+1) add1(dp[i],rval);
// }
// ll ans=1e18;
// rep(i,1,n+1) chkmin(ans,getmin(dp[i]));
// 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: 12112kb
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: 12116kb
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: -100
Wrong Answer
time: 184ms
memory: 70328kb
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:
154816673290
result:
wrong answer 1st lines differ - expected: '154816494865', found: '154816673290'