QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#866904#9222. Price Combolyx123886a123886WA 223ms70312kbC++144.4kb2025-01-22 21:34:202025-01-22 21:34:21

Judging History

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

  • [2025-01-22 21:34:21]
  • 评测
  • 测评结果:WA
  • 用时:223ms
  • 内存:70312kb
  • [2025-01-22 21:34:20]
  • 提交

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'