#include <algorithm>
#include <iostream>
#include <string.h>
#include <cstdlib>
#include <vector>
#include <string>
#include <bitset>
#include <math.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
typedef long long ll;
typedef long double ld;
const ll MOD = 1e9 + 7, INF = 1e18 + 1;
using namespace std;
ll x[1000000], to_diff[1000000], n, c;
vector <int> d;
pair <int, int> diff[1000000], sum[1000000];
struct BIT
{
ll t1[1000000], t2[1000000];
void update (ll x, ll d)
{
for (; x <= n; x |= (x + 1))
{
t1[x] = max (t1[x], d);
t2[x] = min (t2[x], d);
}
}
pair <int, int> get (ll r)
{
ll mx = -INF, mn = INF;
for (;r >= 0; r = (r & (r + 1)) - 1)
{
mx = max (mx, t1[r]);
mn = min (mn, t2[r]);
}
return {mn, mx};
}
void clear ()
{
for (ll i = 0; i < n; i++)
{
t1[i] = -INF;
t2[i] = INF;
}
}
} t_diff, t_sum;
bool check (ll k)
{
cout << k << endl;
t_diff.clear ();
t_sum.clear ();
vector <int> v (n);
ll j = 0;
for (ll i = 0; i < n; i++)
{
while (j < n && diff[j].first < sum[i].first - k)
j++;
cout << diff[j].first << ' ' << sum[i].first << endl;
ll cur = sum[i].second;
v[cur] = j;
cout << cur << ' ' << j << endl;
}
ll min_y_plus_z = -INF, max_y_plus_z = INF;
ll min_y_minus_z = -INF, max_y_minus_z = INF;
for (ll i = 0; i < n; i++)
{
for (ll j = 0; j < i; j++)
{
if (x[i] - x[j] + d[i] + d[j] <= k) continue;
min_y_plus_z = max (min_y_plus_z, (x[j] + d[j]) + (x[i] + d[i]) - k + c);
max_y_plus_z = min (max_y_plus_z, (x[j] - d[j]) + (x[i] - d[i]) + k - c);
cout << i << ' ' << j << ' ' << max_y_plus_z << endl;
min_y_minus_z = max (min_y_minus_z, (x[i] + d[i]) - (x[j] - d[j]) - k + c);
max_y_minus_z = min (max_y_minus_z, (x[i] - d[i]) - (x[j] + d[j]) + k - c);
}
/*pair <int, int> diff_border = t_diff.get (v[i] - 1);
pair <int, int> sum_border = t_sum.get (v[i] - 1);
if (diff_border.first != INF)
{
cout << sum_border.first << ' ' << sum_border.second << endl;
cout << diff_border.first << ' ' << diff_border.second << endl;
if (sum_border.second + x[i] + d[i] - k + c > diff_border.first + (x[i] - d[i]) + k - c) return false;
if (x[i] + d[i] - sum_border.first - k + c > (x[i] - d[i]) - diff_border.second + k - c) return false;
}
t_diff.update (to_diff[i], x[i] - d[i]);
t_sum.update (to_diff[i], x[i] + d[i]);
cout << to_diff[i] << endl;*/
}
cout << min_y_plus_z << ' ' << max_y_plus_z << endl;
cout << min_y_minus_z << ' ' << max_y_minus_z << endl;
if (min_y_plus_z > max_y_plus_z) return false;
if (min_y_minus_z > max_y_minus_z) return false;
for (ll i = 0; i < n; i++)
for (ll j = 0; j < i; j++)
if (min_y_plus_z <= x[i] + x[j] && x[i] + x[j] <= max_y_plus_z &&
min_y_minus_z <= x[i] - x[j] && x[i] - x[j] <= max_y_minus_z)
return true;
return false;
}
ll find_shortcut (ll n, vector <int> l, vector <int> d, ll c)
{
::n = n;
::c = c;
::d = d;
for (ll i = 1; i < n; i++)
{
x[i] = x[i-1] + l[i-1];
}
for (ll i = 0; i < n; i++)
{
scanf ("%d", &d[i]);
sum[i] = {x[i] + d[i], i};
diff[i] = {x[i] - d[i], i};
}
sort (sum, sum + n);
sort (diff, diff + n);
for (ll i = 0; i < n; i++)
to_diff[diff[i].second] = i;
ll L = 0, R = INF;
while (L < R)
{
ll mid = (L + R) / 2;
if (check (mid)) R = mid;
else L = mid + 1;
}
return L;
}
Compilation message
shortcut.cpp: In function 'll find_shortcut(ll, std::vector<int>, std::vector<int>, ll)':
shortcut.cpp:147:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d", &d[i]);
~~~~~~^~~~~~~~~~~~~
/tmp/ccevlaWz.o: In function `main':
grader.cpp:(.text.startup+0x10d): undefined reference to `find_shortcut(int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, int)'
collect2: error: ld returned 1 exit status
