Submission #692067

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef complex<double> P;
typedef pair<int,int> pii;
#define REP(i,n) for(ll i=0;i<n;++i)
#define REPR(i,n) for(ll i=1;i<n;++i)
#define FOR(i,a,b) for(ll i=a;i<b;++i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define MOD (ll)(1e9+7)
#define ADD(a,b) a=((a)+(b))%MOD
#define FIX(a) ((a)%MOD+MOD)%MOD

// Hu-Tucker algorithm
// 間に葉のない二接点の組み合わせの内、和が最小のものを選ぶ
// 右側の接点を削除し、左側の接点に値を追加する
// 左側の接点が葉であった場合それを内点に変更する
// これを実装すれば良い

// 葉→葉という範囲を全て meldable heap で持つ

// 葉 (A) と 葉 (B) の併合の場合
// 葉 (C) - 葉 (A) - 葉 (B) - 葉(D)
// → 葉 (C) - 接点 (AB) - 葉 (D)
// CA, AB, BD 全て併合

// 葉 (A) と 接点 (B) の併合の場合
// 葉 (C) - 葉 (A) - 接点 (B) - 葉 (D)
// → 葉(C) - 接点 (AB) - 葉 (D)
// CA, AD 併合

// 接点 (A) と 接点 (B) の併合の場合
// 葉 (C) - 接点 (A) - 接点 (B) - 葉 (D)
// → 葉 (C) - 接点 (AB) - 葉 (D)
// 変化なし

int n;
int a[125252];

struct seq_data{
  // 最小和、最小ペア左、最小ペア右、列ID
  int sum,left,right,id;
  seq_data(int s,int l,int r,int i):sum(s),left(l),right(r),id(i){}
};
bool operator<(const seq_data &a, const seq_data &b){
  if(a.sum!=b.sum)return a.sum<b.sum;
  if(a.left!=b.left)return a.left<b.left;
  if(a.right!=b.right)return a.right<b.right;
  return a.id<b.id;
}
// queue of pii<minsum,seq_id>
set<seq_data> master_queue;

// sequence sets
multiset<pii> sequence[125252];
// 列左端、列右端
int seq_left[125252], seq_right[125252];
// 前列、後列
int seq_prev[125252], seq_succ[125252];

int getSmallestSum(int id){
  int res = 0;
  multiset<pii>::iterator iter = sequence[id].begin();
  res += iter->first;
  iter++;
  res += iter->first;
  return res;
}

pii getSmallestPair(int id){
  pii ret;
  multiset<pii>::iterator iter = sequence[id].begin();
  ret.first = iter->second;
  iter++;
  ret.second = iter->second;
  if(ret.first > ret.second) swap(ret.first,ret.second);
  return ret;
}

void master_push(int id){
  pii s_p = getSmallestPair(id);
  master_queue.insert(seq_data(
    getSmallestSum(id), s_p.first, s_p.second, id
  ));
}

void master_erase(int id){
  pii s_p = getSmallestPair(id);
  master_queue.erase(seq_data(
    getSmallestSum(id), s_p.first, s_p.second, id
  ));
}

ll hu_tucker(){
  ll ans = 0;
  REP(i,n-1){
    seq_left[i] = i;
    seq_right[i] = i+1;
    seq_prev[i] = i-1;
    seq_succ[i] = i+1;
    sequence[i].insert(pii(a[i],i));
    sequence[i].insert(pii(a[i+1],i+1));
    master_push(i);
  }
  REP(_,n-3){
    seq_data data = *master_queue.begin();
    master_queue.erase(master_queue.begin());
    int sum = data.sum;
    int x = data.left;
    int y = data.right;
    int id = data.id;
    ans += sum;
    // merge
    if(x == seq_left[id] && y == seq_right[id]){
      // merge 3 seq
      int aa = seq_prev[id], b = id, c = seq_succ[id];
      master_erase(aa);
      master_erase(b);
      master_erase(c);
      int leflef = seq_left[aa];
      int rigrig = seq_right[c];
      int prepre = seq_prev[aa], sucsuc = seq_succ[c];
      pii p = pii(a[x],x), q = pii(a[y],y);
      sequence[aa].erase(sequence[aa].find(p));
      sequence[b].erase(sequence[b].find(p));
      sequence[b].erase(sequence[b].find(q));
      sequence[c].erase(sequence[c].find(q));
      a[x] += a[y];
      p = pii(a[x],x);
      if(sequence[b].size()<sequence[c].size()) swap(b,c);
      if(sequence[aa].size()<sequence[b].size()) swap(aa,b);
      multiset<pii>::iterator iter;
      iter = sequence[b].begin();
      while(iter!=sequence[b].end()){
        sequence[aa].insert(*iter);
        ++iter;
      }
      sequence[b].clear();
      iter = sequence[c].begin();
      while(iter!=sequence[c].end()){
        sequence[aa].insert(*iter);
        ++iter;
      }
      sequence[c].clear();
      sequence[aa].insert(p);
      seq_left[aa] = leflef;
      seq_right[aa] = rigrig;
      seq_prev[aa] = prepre;
      seq_succ[aa] = sucsuc;
      if(prepre>=0) seq_succ[prepre] = aa;
      if(sucsuc<n-1) seq_prev[sucsuc] = aa;
      master_push(aa);
    }else if(x == seq_left[id]){
      // merge 2 seq
      int aa = seq_prev[id], b = id;
      master_erase(aa);
      master_erase(b);
      int leflef = seq_left[aa];
      int rigrig = seq_right[b];
      int prepre = seq_prev[aa], sucsuc = seq_succ[b];
      pii p = pii(a[x],x), q = pii(a[y],y);
      sequence[aa].erase(sequence[aa].find(p));
      sequence[b].erase(sequence[b].find(p));
      sequence[b].erase(sequence[b].find(q));
      a[x] += a[y];
      p = pii(a[x],x);
      if(sequence[aa].size()<sequence[b].size()) swap(aa,b);
      multiset<pii>::iterator iter;
      iter = sequence[b].begin();
      while(iter!=sequence[b].end()){
        sequence[aa].insert(*iter);
        ++iter;
      }
      sequence[b].clear();
      sequence[aa].insert(p);
      seq_left[aa] = leflef;
      seq_right[aa] = rigrig;
      seq_prev[aa] = prepre;
      seq_succ[aa] = sucsuc;
      if(prepre>=0) seq_succ[prepre] = aa;
      if(sucsuc<n-1) seq_prev[sucsuc] = aa;
      master_push(aa);
    }else if(y == seq_right[id]){
      // merge 2 seq
      int aa = id, b = seq_succ[id];
      master_erase(aa);
      master_erase(b);
      int leflef = seq_left[aa];
      int rigrig = seq_right[b];
      int prepre = seq_prev[aa], sucsuc = seq_succ[b];
      pii p = pii(a[x],x), q = pii(a[y],y);
      sequence[aa].erase(sequence[aa].find(p));
      sequence[aa].erase(sequence[aa].find(q));
      sequence[b].erase(sequence[b].find(q));
      a[x] += a[y];
      p = pii(a[x],x);
      if(sequence[aa].size()<sequence[b].size()) swap(aa,b);
      multiset<pii>::iterator iter;
      iter = sequence[b].begin();
      while(iter!=sequence[b].end()){
        sequence[aa].insert(*iter);
        ++iter;
      }
      sequence[b].clear();
      sequence[aa].insert(p);
      seq_left[aa] = leflef;
      seq_right[aa] = rigrig;
      seq_prev[aa] = prepre;
      seq_succ[aa] = sucsuc;
      if(prepre>=0) seq_succ[prepre] = aa;
      if(sucsuc<n-1) seq_prev[sucsuc] = aa;
      master_push(aa);
    }else{
      // no merge only delete
      master_erase(id);
      pii p = pii(a[x],x), q = pii(a[y],y);
      sequence[id].erase(sequence[id].find(p));
      sequence[id].erase(sequence[id].find(q));
      a[x] += a[y];
      p = pii(a[x],x);
      sequence[id].insert(p);
      master_push(id);
    }
  }
  return ans;
}

int main(){
  scanf("%d",&n);
  REP(i,n)scanf("%lld",a+i+1);
  a[0] = 1e9;
  a[n+1] = 1e9;
  n += 2;
  ll ans = hu_tucker();
  printf("%lld\n",ans);
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:238:29: warning: format ‘%lld’ expects argument of type ‘long long int*’, but argument 2 has type ‘int*’ [-Wformat=]
   REP(i,n)scanf("%lld",a+i+1);
                             ^
./Main.cpp:237:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&n);
                 ^
./Main.cpp:238:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   REP(i,n)scanf("%lld",a+i+1);
                              ^

Judge Result