Cerinta completa
Airports are being built on a straight road according to a new construction plan. For convenience, imagine a number line on which at different points airports can be positioned. Because a plane can’t take off and start landing immediately, there will be flight between two airports in locations and if and only if , where is a constant.
Changing the position of an airport from to costs . The cost to fix a certain plan is the minimum total cost of changing the positions of airports. After the changes, it should be possible to travel between any pair of airports, possibly taking flights through some intermediate airports. Note that it’s possible that two airports have the same initial position, and this can be the case after changes too.
On day, a plan to build a new airport with position is announced. On each day that a new airport is announced, print the smallest cost to fix the set of airports announced so far . Note that you should not change the positions of any airports, just calculate the cost to do it.
Input Format
Input contains multiple queries.
The first line consists of an integer which is the number of queries. Each query is given as follows.
The first line of each query contains two integers and , the number of days, and the minimum distance respectively.
The second line of each test case contains space-separated integers denoting the position of the airport that was announced on day.
Constraints
- the sum of over all test cases in a file will not exceed
Output Format
Print one line for each query.
A line for a query with airports should have numbers on it where the one should be the minimum cost to fix airports in positions .
Sample Input 0
1
3 1
0 0 0
Sample Output 0
0 1 1
Explanation 0
The answer for a single airport is always zero. When we have many airports in the same position, it’s enough to move only one of them to satisfy the condition from the statement.
Sample Input 1
1
5 4
1 -1 2 -1 1
Sample Output 1
0 2 2 3 3
Explanation 1
For each new day that an airport is inserted, the cheapest rearranging of existing airports is shown on the diagram above. Note that cost changes for every day and travelling between airports can be done possibly flying through some intermediate ones. Costs are calculated without changing actual positions of the airports.
Limbajul de programare folosit: cpp14
Cod:
// ayy
// ' lamo
// SUBLIME HAX
#include <bits/stdc++.h>
using namespace std;
template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &x) {
return os << "(" << x.first << "," << x.second << ")";
}
namespace dbg_ns {
template <typename C> struct is_iterable {
template <class T> static long check(...);
template <class T>
static char check(int, typename T::const_iterator = C().end());
enum {
value = sizeof(check<C>(0)) == sizeof(char),
neg_value = sizeof(check<C>(0)) != sizeof(char)
};
};
template <class T> ostream &_out_str(ostream &os, const T &x) {
return os << '"' << x << '"';
}
template <class T> ostream &_dbg2_5(ostream &, const T &);
template <bool B, typename T = void> using eit = typename enable_if<B, T>::type;
template <class T>
inline ostream &_dbg3(ostream &os, eit<is_iterable<T>::neg_value, const T> &x) {
return os << x;
}
template <class T>
inline ostream &_dbg3(ostream &os, eit<is_iterable<T>::value, const T> &V) {
os << "{";
bool ff = 0;
for (const auto &E : V)
_dbg2_5(ff ? os << "," : os, E), ff = 1;
return os << "}";
}
template <> inline ostream &_dbg3<string>(ostream &os, const string &x) {
return _out_str(os, x);
}
template <>
inline ostream &_dbg3<const char *>(ostream &os, const char *const &x) {
return _out_str(os, x);
}
template <class T> inline ostream &_dbg2_5(ostream &os, const T &x) {
return _dbg3<T>(os, x);
}
template <class T, typename... Args>
ostream &_dbg2(ostream &os, vector<string>::iterator nm, const T &x,
Args &&... args);
inline ostream &_dbg2(ostream &os, vector<string>::iterator) { return os; }
template <typename... Args>
inline ostream &_dbg2(ostream &os, vector<string>::iterator nm, const char *x,
Args &&... args) {
return _dbg2(_dbg3<const char *>(os << " ", x), nm + 1, args...);
}
template <class T, typename... Args>
inline ostream &_dbg2(ostream &os, vector<string>::iterator nm, const T &x,
Args &&... args) {
return _dbg2(_dbg3<T>(os << " " << *nm << "=", x), nm + 1, args...);
}
vector<string> split(string s) {
vector<string> Z;
string z = "";
s += ',';
int dep = 0;
for (char c : s) {
if (c == ',' && !dep)
Z.push_back(z), z = "";
else
z += c;
if (c == '(')
++dep;
if (c == ')')
--dep;
}
return Z;
}
template <typename... Args>
inline ostream &_dbg1(int ln, const string &nm, Args &&... args) {
auto nms = split(nm);
return _dbg2(cerr << "L" << ln << ":", nms.begin(), args...) << endl;
}
} // namespace dbg_ns
#define dbg(...) dbg_ns::_dbg1(__LINE__, #__VA_ARGS__, __VA_ARGS__)
#define sz(x) (int(x.size()))
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define fi first
#define se second
#define pb push_back
// END SUBLIME HAX
// #include <bits/extc++.h>
// using namespace __gnu_pbds;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld; // CARE
typedef complex<ld> pt;
const ld eps = (ld)1e-8;
const ld tau = 2 * (ld)acosl(-1);
const int inf = 1e9 + 99;
const ll linf = 1e18 + 99;
const int P = 1e9 + 7;
int n;
int hi, lo;
set<int> ss;
set<pair<int, int>> ww;
void kill(int x) {
auto it = ss.lower_bound(x);
assert(*it == x);
++it;
if (it == ss.end())
return;
int y = *it;
pair<int, int> key = {y - x, x};
if (ww.count(key))
ww.erase(key);
}
void add(int x) {
auto it = ss.lower_bound(x);
assert(*it == x);
++it;
if (it == ss.end())
return;
int y = *it;
ww.insert({y - x, x});
}
void ins(int x) {
auto it = ss.lower_bound(x);
if (it != ss.end() && *it == x)
return;
int y = inf;
if (it != ss.begin()) {
--it;
y = *it;
kill(y);
}
ss.insert(x);
if (y != inf)
add(y);
add(x);
}
void RZ() {
n = 0;
ss.clear();
ww.clear();
}
void INS(int x) {
if (!n) {
hi = lo = x;
n = 1;
return;
}
if (n == 1) {
hi = max(hi, x);
lo = min(lo, x);
n = 2;
return;
}
++n;
if (x > hi) {
ins(hi);
hi = x;
return;
}
if (x < lo) {
ins(lo);
lo = x;
return;
}
ins(x);
}
int Q(int d) {
if (n == 1)
return 0;
assert(sz(ss) <= n - 2);
if (n == 2)
return max(0, d - (hi - lo));
// dbg(ss,ww,lo,hi);
int Z = inf;
auto it = ss.lower_bound(hi - d + 1);
if (it == ss.end())
return 0;
if (*it >= lo + d)
return 0;
Z = min(Z, max(0, d - (*it - lo)));
it = ss.lower_bound(lo + d);
--it;
Z = min(Z, max(0, d - (hi - *it)));
for (;;) {
auto it = ww.end();
if (it == ww.begin()) {
break;
}
--it;
if (it->se < hi - d || it->se + it->fi > lo + d) {
ww.erase(it);
} else {
break;
}
}
auto it2 = ww.end();
if (it2 != ww.begin()) {
--it2;
Z = min(Z, max(0, d + d - (hi - lo) - it2->fi));
}
return Z;
}
void _m() {
int n, d;
scanf("%d%d", &n, &d);
RZ();
for (; n--;) {
int x;
scanf("%d", &x);
INS(x);
printf("%d%c", Q(d), " \n"[!n]);
}
}
int32_t main() {
int q;
scanf("%d", &q);
for (; q--;)
_m();
}
Scor obtinut: 1.0
Submission ID: 464650172
Link challenge: https://www.hackerrank.com/challenges/airports/problem