QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#685532#9222. Price Combo11d10xyWA 431ms49368kbC++142.5kb2024-10-28 19:58:422024-10-28 19:58:42

Judging History

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

  • [2024-10-28 19:58:42]
  • 评测
  • 测评结果:WA
  • 用时:431ms
  • 内存:49368kb
  • [2024-10-28 19:58:42]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using i64=long long;
int n;
namespace ds{
struct N1_{
   i64 s[2];int t;
   N1_ operator+(const N1_&o)const{
      N1_ r{};r.t=t^o.t;
      for(int w:{0,1})r.s[w]=o.s[w]+s[w^o.t];
      return r;
   }
}tag[200010<<2];
struct N_{
   N1_ s;i64 res[2][2];
   N_ operator+(const N_&o)const{
      N_ r{};
      r.s=s+o.s;
      for(int x:{0,1})for(int y:{0,1}){
         r.res[x][y]=min(res[x][y],o.res[x][y^s.t]+s.s[y^s.t^1]);
      }return r;
   }
}t[200010<<2];
inline void pushup(int u){
   t[u]=t[u<<1]+t[u<<1|1];
}
inline void add(int u,N1_ x){
   tag[u]=x+tag[u];
   for(int o:{0,1})for(int w:{0,1})
   t[u].res[o][w]+=x.s[o^1];
   if(x.t&1)swap(t[u].res[0],t[u].res[1]);
}
inline void pushdown(int u){
   add(u<<1,tag[u]),add(u<<1|1,tag[u]),tag[u]={};
}
void mdf(int u,int l,int r,int L,int R,N1_ x){
   if(L<=l&&r<=R)return add(u,x),void();
   int mid=l+r>>1;pushdown(u);
   if(L<=mid)mdf(u<<1,l,mid,L,R,x);
   if(R>mid)mdf(u<<1|1,mid+1,r,L,R,x);
   pushup(u);
}
void insert(int u,int l,int r,int p,N_ w){
   if(l==r)return t[u]=w,void();
   int mid=l+r>>1;pushdown(u);
   if(p<=mid)insert(u<<1,l,mid,p,w);
   else insert(u<<1|1,mid+1,r,p,w);
   pushup(u);
}
N_ qsuf(int u,int l,int r,int L){
   if(L<=l)return t[u];
   int mid=l+r>>1;pushdown(u);
   if(L<=mid)return qsuf(u<<1,l,mid,L)+t[u<<1|1];
   else return qsuf(u<<1,mid+1,r,L);
}
void build(int u,int l,int r){
   if(l==r){
      for(int x:{0,1})for(int y:{0,1})
      t[u].res[x][y]=1e18;
      if(l==n+1||l==0)t[u].res[0][0]=0;
      return;
   }
   int mid=l+r>>1;
   build(u<<1,l,mid),build(u<<1|1,mid+1,r);
   pushup(u);
}
}
int a[200010],b[200010],bid[200010],perm[200010];
int main(){
   scanf("%d",&n);
   for(int i=1;i<=n;i++)scanf("%d",&a[i]);
   for(int i=1;i<=n;i++)scanf("%d",&b[i]);
   for(int i=1;i<=n;i++)perm[i]=i;
   sort(perm+1,perm+n+1,[](int x,int y){
      return a[x]>a[y];
   });
   vector<pair<int,int>>W;
   for(int i=1;i<=n;i++)W.emplace_back(b[i],i);
   sort(begin(W),end(W));
   for(int i=0;i<n;i++)bid[W[i].second]=i+1;
   ds::build(1,0,n+1);
   for(int i=1;i<=n;i++){
      int u=perm[i];
      auto res=ds::qsuf(1,0,n+1,bid[u]);
      swap(res.res[0],res.res[1]);
      for(int o:{0,1})res.res[1][o]+=a[u];
      res.s={{0,b[u]},1};
      ds::mdf(1,0,n+1,0,bid[u],{{0,a[u]},1});
      ds::insert(1,0,n+1,bid[u],res);
   }
   i64 ans=1e18;
   for(int x:{0,1})for(int y:{0,1}){
      ans=min(ans,ds::t[1].res[x][y]);
   }
   printf("%lld",ans);
   return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 5916kb

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: 1ms
memory: 5868kb

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: 431ms
memory: 49368kb

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:

121170953783

result:

wrong answer 1st lines differ - expected: '154816494865', found: '121170953783'