Official

I - Octopus Editorial by en_translator Editorial for printing


First, we consider how can we determine if it can grab \(N\) treasures while satisfying the conditions in the problem statement when its head is at \(x=k_0\).

Consider a sequence \((Y_1,Y_2, \ldots, Y_N)\) consisting of the distances from the head to each treasure, \(\lvert X_i-k_0\rvert\) \((1\leq i\leq N)\), sorted in ascending order.
If \(Y_i\leq L_i\) holds for all \(1\leq i\leq N\), then it can grab them while satisfying the conditions, specifically by using the \(i\)-th leg to grab the treasure distant by \(Y_i\) from the head.
On the other hand, if \(Y_i>L_i\), then there is no conforming way to grab the treasure, because at least \((N-i+1)\) treasures are distant from the head by at least \((L_i+1)\), but there are at most \((N-i)\) legs that can grab them.

Naively, one can sort \((Y_1,Y_2,\ldots,Y_N)\) in an \(O(N\log N)\) time using algorithms like quick sort, or one can even inspect the nearest treasures to \(x=k_0\) on both sides in a total of \(O(N)\) time, so the decision problem can be solved in a total of \(O(N\log N)\) or \(O(N)\) time.

However, the range of the candidates of the head is \(-2\times 10^{18}\leq x\leq 2\times 10^{18}\), so it is almost impossible to consider it for all such candidates within the time limit. Instead, we consider when does the answer change from \(x=k_0\) to \(x=k_0+1\).

  • If \(x=k_0\) satisfies the condition, but \(x=k_0+1\) does not

In this case, a valid correspondence between a leg and a treasure in \(x=k_0\) should become invalid. That is, there should be \(1\leq i,j\leq N\) such that \(k_0-L_j\leq X_i\leq k_0+L_j\) and (\(X_i<k_0+1-L_j\) or \(k_0+1+L_j<X_i\)). Such \(k_0\), which should be an integer, is limited to those with \(k_0=X_i+L_j\), so there are at most \(N^2\) such candidates.

  • If \(x=k_0\) does not satisfy the condition, but \(x=k_0+1\) does

In this case, an invalid correspondence between a leg and a treasure in \(x=k_0\) should become valid. That is, there should be \(1\leq i,j\leq N\) such that \(k_0+1-L_j\leq X_i\leq k_0+1+L_j\) and (\(X_i<k_0-L_j\) or \(k_0+L_j<X_i\)). Such \(k_0\), which should be an integer, is limited to those with \(k_0=X_i-L_j-1\), so there are at most \(N^2\) such candidates too.

Therefore, the set \(S=\{X_i+L_j|1\leq i,j\leq N \}\bigcup \{X_i-L_j-1|1\leq i,j\leq N \}\) has at most \(2N^2\) elements. When its elements are sorted in ascending order as \(S_1,S_2,\ldots,S_{|S|}\), then for each \(2\leq i\leq |S|\), all \(x\) with \(S_{i-1}+1\leq x\leq S_i\) satisfy the condition if and only if \(x=S_i\) does. Here, those within \(x\leq S_1\) and \(S_{|S|}+1\leq x\) never satisfies the condition because it is impossible to satisfy the condition when the head is far enough.

Therefore, it is sufficient to determine if \(x=S_i\) satisfies the condition for each \(2\leq i\leq |S|\).
Enumerating and sorting the elements of \(S\) costs \(O(N^2\log N)\), and checking each element costs a total of \(O(N^3)\) (or \(O(N^3\log N)\)) time, so the problem has been solved fast enough.

Sample code in C++:

#include <bits/stdc++.h>
using namespace std;

int n;
vector<long long>l,x;

bool judge(long long k){
  int le=-1,ri=0,nx;
  for(int i=0;i<n;i++){
    if(x[i]<k)le++,ri++;
    else break;
  }
  for(int i=0;i<n;i++){
    if(le<0)nx=ri,ri++;
    else if(ri>=n)nx=le,le--;
    else if((k-x[le])>(x[ri]-k))nx=ri,ri++;
    else nx=le,le--;
    if(abs(x[nx]-k)>l[i])return false;
  }
  return true;
}


int main(void) {
  long long val,ans=0;
  vector<long long>s;

	cin>>n;
  for(int i=0;i<n;i++){
    cin>>val;
    x.push_back(val);
  }
  for(int i=0;i<n;i++){
    cin>>val;
    l.push_back(val);
  }

  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      s.push_back(x[i]+l[j]);
      s.push_back(x[i]-l[j]-1);
    }
  }
  sort(s.begin(),s.end());

  int sz=s.size();
  for(int i=1;i<sz;i++){
    if(judge(s[i]))ans+=s[i]-s[i-1];
  }
  cout<<ans<<endl;
  return 0;
}

posted:
last update: