nile — IOI contest
Task type: batch | Time limit: 2 s | Memory limit: 2048 MB | Difficulty: 20
Algorithms: data structure, segment tree, disjoint set, offline queries

# Nile

You want to transport $N$ artifacts through the Nile. 
The artifacts are numbered from $0$ to $N-1$.
The weight of artifact $i$ ($0 \leq i < N$) is $W[i]$.

To transport the artifacts, you use specialized boats.
Each boat can carry **at most two** artifacts.

* If you decide to put a single artifact in a boat, the artifact weight can be arbitrary.
* If you want to put two artifacts in the same boat, you have to make sure the boat is balanced evenly.
Specifically, you can send
 artifacts $p$ and $q$ ($0 \leq p < q < N$) in the same boat
  only if the absolute difference between their weights is at most $D$,
 that is $|W[p] - W[q]| \leq D$.

To transport an artifact, you have to pay a cost
 that depends on the number of artifacts carried in the same boat.
The cost of transporting artifact $i$ ($0 \leq i < N$) is:

* $A[i]$, if you put the artifact in its own boat, or
* $B[i]$, if you put it in a boat together with some other artifact.

Note that in the latter case, you have to pay for both artifacts in the boat.
Specifically, if you decide to send
 artifacts $p$ and $q$ ($0 \leq p < q < N$) in the same boat,
 you need to pay $B[p] + B[q]$.

Sending an artifact in a boat by itself is always more expensive 
than sending it with some other artifact sharing the boat with it,
so $B[i] < A[i]$ for all $i$ such that $0 \leq i < N$.

Unfortunately, the river is very unpredictable and the value of $D$ changes often.
Your task is to answer $Q$ questions numbered from $0$ to $Q-1$.
The questions are described by an array $E$ of length $Q$.
The answer to question $j$ ($0 \leq j < Q$) is
 the minimum total cost of transporting all $N$ artifacts,
 when the value of $D$ is equal to $E[j]$.

## Implementation Details

You should implement the following procedure.

```
std::vector&lt;long long&gt; calculate_costs(
    std::vector&lt;int&gt; W, std::vector&lt;int&gt; A, 
    std::vector&lt;int&gt; B, std::vector&lt;int&gt; E)
```

* $W$, $A$, $B$: arrays of integers of length $N$, describing the weights of the artifacts and the costs of transporting them.
* $E$: an array of integers of length $Q$ describing the value of $D$ for each question.
* This procedure should return an array $R$ of $Q$ integers
   containing the minimum total cost of transporting the artifacts,
   where $R[j]$ gives the cost when the value of $D$ is $E[j]$ (for each $j$
   such that $0 \leq j < Q$).
* This procedure is called exactly once for each test case.

## Constraints

* $1 \leq N \leq 100\,000$
* $1 \leq Q \leq 100\,000$
* $1 \leq W[i] \leq 10^{9}$
   for each $i$ such that $0 \leq i < N$
* $1 \leq B[i] < A[i] \leq 10^{9}$
   for each $i$ such that $0 \leq i < N$
* $1 \leq E[j] \leq 10^{9}$
   for each $j$ such that $0 \leq j < Q$

## Subtasks

| Subtask | Score  | Additional Constraints |
| :-----: | :----: | ---------------------- |
| 1       | $6$    | $Q \leq 5$; $N \leq 2000$; $W[i] = 1$ for each $i$ such that $0 \leq i < N$
| 2       | $13$   | $Q \leq 5$; $W[i] = i+1$ for each $i$ such that $0 \leq i < N$
| 3       | $17$   | $Q \leq 5$; $A[i] = 2$ and $B[i] = 1$ for each $i$ such that $0 \leq i < N$
| 4       | $11$   | $Q \leq 5$; $N \leq 2000$
| 5       | $20$   | $Q \leq 5$
| 6       | $15$   | $A[i] = 2$ and $B[i] = 1$ for each $i$ such that $0 \leq i < N$
| 7       | $18$   | No additional constraints.

## Example

Consider the following call.

```
calculate_costs([15, 12, 2, 10, 21],
                [5, 4, 5, 6, 3],
                [1, 2, 2, 3, 2],
                [5, 9, 1])
```

In this example we have $N = 5$ artifacts and $Q = 3$ questions.

In the first question, $D = 5$.
You can send artifacts $0$ and $3$ in one boat (since $|15 - 10| \leq 5$) and the remaining artifacts in separate boats.
This yields the minimum cost of transporting all the artifacts, which is $1+4+5+3+3 = 16$.

In the second question, $D = 9$.
You can send artifacts $0$ and $1$ in one boat (since $|15 - 12| \leq 9$) and send artifacts $2$ and $3$ in one boat (since $|2 - 10| \leq 9$).
The remaining artifact can be sent in a separate boat.
This yields the minimum cost of transporting all the artifacts, which is $1+2+2+3+3 = 11$.

In the final question, $D = 1$. You need to send each artifact in its own boat.
This yields the minimum cost of transporting all the artifacts, which is $5+4+5+6+3 = 23$.

Hence, this procedure should return $[16, 11, 23]$.


## Sample Grader

Input format:

```
N
W[0] A[0] B[0]
W[1] A[1] B[1]
...
W[N-1] A[N-1] B[N-1]
Q
E[0]
E[1]
...
E[Q-1]
```

Output format:

```
R[0]
R[1]
...
R[S-1]
```

Here, $S$ is the length of the array $R$ returned by `calculate_costs`.


Starter code:
grader.cpp: #include "nile.h"
#include <cassert>
#include <cstdio>
#include <vector>

int main() {
  int N;
  assert(1 == scanf("%d", &N));
  std::vector<int> W(N), A(N), B(N);
  for (int i = 0; i < N; i++)
    assert(3 == scanf("%d%d%d", &W[i], &A[i], &B[i]));
  int Q;
  assert(1 == scanf("%d", &Q));
  std::vector<int> E(Q);
  for (int j = 0; j < Q; j++)
    assert(1 == scanf("%d", &E[j]));
  fclose(stdin);

  std::vector<long long> R = calculate_costs(W, A, B, E);

  int S = (int)R.size();
  for (int j = 0; j < S; j++)
    printf("%lld\n", R[j]);
  fclose(stdout);

  return 0;
}

nile.cpp: #include "nile.h"

std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A,
                                       std::vector<int> B, std::vector<int> E) {
  int Q = (int)E.size();
  std::vector<long long> R(Q, 0);
  return R;
}

nile.h: #include <vector>

std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A,
                                       std::vector<int> B, std::vector<int> E);

grader_cms.cpp: #include "nile.h"
#include <cassert>
#include <cstdio>
#include <vector>
// BEGIN SECRET
#include <cstdlib>
#include <string>

namespace {

void write_grader_result(std::string grader_result, std::string grader_msg = "") {
  const std::string output_secret = "4FBwMMwcdlgPodEtp0owUlxQgA5SuIlq";
  printf("%s\n", output_secret.c_str());
  printf("%s\n", grader_result.c_str());
  if (!grader_msg.empty())
    printf("%s\n", grader_msg.c_str());
  fflush(stdout);
}

bool exit_allowed = false;

void authorized_exit(int exit_code) {
  exit_allowed = true;
  exit(exit_code);
}

void check_exit_protocol() {
  if (!exit_allowed)
    write_grader_result("PV", "Solution called exit()");
}

} // namespace
// END SECRET

int main() {
  // BEGIN SECRET
  atexit(check_exit_protocol);
  at_quick_exit(check_exit_protocol);
  exit_allowed = true;

  const std::string input_secret = "1U22aPSRkiGgB7zXbfJs9IqSfacMQ9t7";
  char secret[1000];
  assert(1 == scanf("%999s", secret));
  if (std::string(secret) != input_secret) {
    write_grader_result("PV", "Possible tampering with the input");
    fclose(stdout);
    authorized_exit(0);
  }
  // END SECRET
  int N;
  assert(1 == scanf("%d", &N));
  std::vector<int> W(N), A(N), B(N);
  for (int i = 0; i < N; i++)
    assert(3 == scanf("%d%d%d", &W[i], &A[i], &B[i]));
  int Q;
  assert(1 == scanf("%d", &Q));
  std::vector<int> E(Q);
  for (int j = 0; j < Q; j++)
    assert(1 == scanf("%d", &E[j]));
  fclose(stdin);
  // BEGIN SECRET
  exit_allowed = false;
  // END SECRET

  std::vector<long long> R = calculate_costs(W, A, B, E);

  // BEGIN SECRET
  if ((int)R.size() != Q) {
    write_grader_result("WA", "Returned array R is not of length Q");
    fclose(stdout);
    authorized_exit(0);
  }
  write_grader_result("OK");
  // END SECRET
  int S = (int)R.size();
  for (int j = 0; j < S; j++)
    printf("%lld\n", R[j]);
  fclose(stdout);

  // BEGIN SECRET
  exit_allowed = true;
  // END SECRET
  return 0;
}