Original proposer: admin

There are various solutions to this problem. In this editorial, we will introduce an off-line solution, which finds the \(i\)-th answer without receiving the \((i+1)\)-th input.

First, consider what happens when a person arrives.
Suppose that a person has arrived as the \(k\)-th position from the left.
Then, the distance to the closest person may have changed for only the \((k-1)\)-th, \(k\)-th, and \((k+1)\)-th persons from the left (including the person who has just arrived). Let us call these persons \(x\), \(y\), and \(z\).
This implies that when a person arrives, we do not recalculate the distance for all people, and update only these three.

This kind of technique, where only the affected factors are recalculated, is called differential update. This technique is important not only in Algorithm, but also Heuristic contests.

Now we will describe two approaches.

Approach 1. Naively update these three persons

The differential updates can be applied by the following steps.

• For persons \(x\) and \(z\), find the shortest distances to other people (before person \(y\) arrives), and subtract them from the answer.
• Insert \(y\).
• For persons \(x\), \(y\), and \(z\), find the shortest distances to other people, and add them to the answer.

Approach 2. Simply the differential updates using the property of the problem

In this problem, “the shortest distance to another person” never increases by an insertion. This allows us to perform differential updates in the following way:

• For \(x,z\), compare the distance to the closest other person with the distance to \(y\), and set it to the smaller of them.
• For \(y\), set it to the distance to the closer person of \(x\) and \(z\).

Approach 1 is effective when there is no good property in deltas, while approach 2 is effective when there is a good property and helps reducing the computational complexity, so we recommend you to understand both ways.

Both of the following sample code runs in \(O(N \log N)\) time.

Approach 1 sample code (C++):

#include<bits/stdc++.h>

using namespace std;

int nearest(int x,set<int> &st){
  auto it=st.find(x);
  int res=2e9;
  if(it!=st.begin()){
    auto jt=it; jt--;
    res=min(res,x-(*jt));
  }
  it++;
  if(it!=st.end()){
    res=min(res,(*it)-x);
  }
  return res;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n;
  cin >> n;
  int res=0;
  set<int> st;
  {
    int x;
    cin >> x;
    st.insert(0);
    st.insert(x);
    res+=2*x;
    cout << res << "\n";
  }
  for(int i=1;i<n;i++){
    int x;
    cin >> x;
    vector<int> hit;
    auto it=st.lower_bound(x);
    if(it!=st.end()){hit.push_back(*it);}
    if(it!=st.begin()){
      it--;
      hit.push_back(*it);
    }
    for(auto &nx : hit){
      res-=nearest(nx,st);
    }
    st.insert(x);
    hit.push_back(x);
    for(auto &nx : hit){
      res+=nearest(nx,st);
    }
    cout << res << "\n";
  }
  return 0;
}

Approach 2 sample code (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n;
  cin >> n;
  int res=0;
  set<int> st;
  map<int,int> mp;
  {
    int x;
    cin >> x;
    st.insert(0);
    st.insert(x);
    mp[0]=x;
    mp[x]=x;
    res+=2*x;
    cout << res << "\n";
  }
  for(int i=1;i<n;i++){
    int x;
    cin >> x;
    vector<int> hit;
    auto it=st.lower_bound(x);
    if(it!=st.end()){hit.push_back(*it);}
    if(it!=st.begin()){
      it--;
      hit.push_back(*it);
    }
    st.insert(x);
    mp[x]=2e9;
    for(auto &nx : hit){
      res-=mp[nx];
      mp[nx]=min(mp[nx],abs(nx-x));
      res+=mp[nx];
      mp[x]=min(mp[x],abs(nx-x));
    }
    res+=mp[x];
    cout << res << "\n";
  }
  return 0;
}

Bonus!
In the sample code, we manage the answers in a variable of type int (that stores integers up to about \(2.1 \times 10^9\)), but this is not a bug. Why?