#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6;
int64_t a[N], b[N], x[N];
int orda[N], ordb[N];
int n, c;
pair<int, int> max_a(-1, -1), min_b(-1, -1);
int64_t get(int64_t o[], const pair<int, int>& v, const int& j, const int64_t& inf) {
if (v.first == -1) return inf;
if (v.first == j) return v.second == -1 ? inf : o[v.second];
return o[v.first];
};
inline void update(int j) {
if (max_a.first == -1 || a[j] >= a[max_a.first]) {
swap(max_a.first, max_a.second);
max_a.first = j;
} else if (max_a.second == -1 || a[j] > a[max_a.second]) {
max_a.second = j;
}
if (min_b.first == -1 || b[j] <= b[min_b.first]) {
swap(min_b.first, min_b.second);
min_b.first = j;
} else if (min_b.second == -1 || b[j] < b[min_b.second]) {
min_b.second = j;
}
};
inline bool check(const int64_t& target) {
int64_t low_sum = -1e18, high_sum = +1e18;
int64_t low_diff = -1e18, high_diff = +1e18;
const int64_t k = c - target;
max_a = min_b = make_pair(-1, -1);
int i = 0;
for (int z = 0; z < n; z++) {
int j = orda[z];
while (i < n && a[j] - b[ordb[i]] > target) update(ordb[i++]);
low_sum = max(low_sum, a[j] + get(a, max_a, j, -1e18) + k);
high_sum = min(high_sum, b[j] + get(b, min_b, j, +1e18) - k);
low_diff = max(low_diff, a[j] - get(b, min_b, j, +1e18) + k);
high_diff = min(high_diff, b[j] - get(a, max_a, j, -1e18) - k);
if (low_sum > high_sum || low_diff > high_diff) return 0;
}
int low_sum_q = n - 1, low_diff_q = 0, high_sum_q = n - 1, high_diff_q = 0;
for (int p = 0; p < n; p++) {
low_diff_q = max(low_diff_q, p + 1);
while (low_sum_q > p && x[p] + x[low_sum_q] >= low_sum) low_sum_q--;
while (high_sum_q > p && x[p] + x[high_sum_q] > high_sum) high_sum_q--;
// (low_sum_q, high_sum_q]
while (low_diff_q < n && x[low_diff_q] - x[p] < low_diff) low_diff_q++;
high_diff_q = max(high_diff_q, low_diff_q);
while (high_diff_q < n && x[high_diff_q] - x[p] <= high_diff) high_diff_q++;
// [low_diff_q, high_diff_q)
low_sum_q = max(low_sum_q, p);
if (low_sum_q >= high_sum_q || low_diff_q >= high_diff_q) continue;
int max_l = max(low_sum_q + 1, low_diff_q);
int min_r = min(high_sum_q, high_diff_q - 1);
if (max_l <= min_r) {
return 1;
}
}
return 0;
};
long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c) {
::n = n, ::c = c;
for (int i = 1; i < n; i++) x[i] = x[i - 1] + l[i - 1];
for (int i = 0; i < n; i++) a[i] = x[i] + d[i], b[i] = x[i] - d[i];
// abs(x[i] - x[p]) + abs(x[j] - x[q]) + d[i] + d[j] + c <= target
// x[i] - x[p] + x[j] - x[q] + d[i] + d[j] + c <= target
// x[p] - x[i] + x[j] - x[q] + d[i] + d[j] + c <= target
// x[i] - x[p] + x[q] - x[j] + d[i] + d[j] + c <= target
// x[p] - x[i] + x[q] - x[j] + d[i] + d[j] + c <= target
// x[p] + x[q] >= x[i] + x[j] + d[i] + d[j] + c - target
// x[p] + x[q] <= x[i] + x[j] - d[i] - d[j] - c + target
// x[q] - x[p] <= x[j] - x[i] - d[i] - d[j] - c + target
// x[q] - q[p] >= x[j] - x[i] + d[i] + d[j] + c - target
// k := c - target
// x[p] + x[q] >= (x[i] + d[i]) + (x[j] + d[j]) + k
// x[p] + x[q] <= (x[i] - d[i]) + (x[j] - d[j]) - k
// x[q] - x[p] <= (x[j] - d[j]) - (x[i] + d[i]) - k
// x[q] - x[p] >= (x[j] + d[j]) - (x[i] - d[i]) + k
// x[p] + x[q] >= a[i] + a[j] + k
// x[p] + x[q] <= b[i] + b[j] - k
// x[q] - x[p] <= b[j] - a[i] - k
// x[q] - x[p] >= a[j] - b[i] + k
iota(orda, orda + n, 0);
sort(orda, orda + n, [&](int i, int j) { return a[i] < a[j]; });
iota(ordb, ordb + n, 0);
sort(ordb, ordb + n, [&](int i, int j) { return b[i] < b[j]; });
int64_t low = 1, high = 1e15 + 2e9;
while (low < high) {
int64_t mid = low + high >> 1;
if (check(mid)) {
high = mid;
} else {
low = mid + 1;
}
}
return high;
}
Compilation message
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/gthr.h:148,
from /usr/include/c++/10/ext/atomicity.h:35,
from /usr/include/c++/10/bits/ios_base.h:39,
from /usr/include/c++/10/ios:42,
from /usr/include/c++/10/istream:38,
from /usr/include/c++/10/sstream:38,
from /usr/include/c++/10/complex:45,
from /usr/include/c++/10/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
from shortcut.cpp:5:
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:102:1: error: attribute value 'tune=native' was already specified in 'target' attribute
102 | __gthrw(pthread_once)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:102:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:103:1: error: attribute value 'tune=native' was already specified in 'target' attribute
103 | __gthrw(pthread_getspecific)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:103:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:104:1: error: attribute value 'tune=native' was already specified in 'target' attribute
104 | __gthrw(pthread_setspecific)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:104:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:106:1: error: attribute value 'tune=native' was already specified in 'target' attribute
106 | __gthrw(pthread_create)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:106:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:107:1: error: attribute value 'tune=native' was already specified in 'target' attribute
107 | __gthrw(pthread_join)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:107:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:108:1: error: attribute value 'tune=native' was already specified in 'target' attribute
108 | __gthrw(pthread_equal)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:108:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:109:1: error: attribute value 'tune=native' was already specified in 'target' attribute
109 | __gthrw(pthread_self)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:109:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:110:1: error: attribute value 'tune=native' was already specified in 'target' attribute
110 | __gthrw(pthread_detach)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:110:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:112:1: error: attribute value 'tune=native' was already specified in 'target' attribute
112 | __gthrw(pthread_cancel)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:112:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:114:1: error: attribute value 'tune=native' was already specified in 'target' attribute
114 | __gthrw(sched_yield)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:114:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:116:1: error: attribute value 'tune=native' was already specified in 'target' attribute
116 | __gthrw(pthread_mutex_lock)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:116:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:117:1: error: attribute value 'tune=native' was already specified in 'target' attribute
117 | __gthrw(pthread_mutex_trylock)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:117:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:119:1: error: attribute value 'tune=native' was already specified in 'target' attribute
119 | __gthrw(pthread_mutex_timedlock)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:119:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:121:1: error: attribute value 'tune=native' was already specified in 'target' attribute
121 | __gthrw(pthread_mutex_unlock)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:121:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:122:1: error: attribute value 'tune=native' was already specified in 'target' attribute
122 | __gthrw(pthread_mutex_init)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:122:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:123:1: error: attribute value 'tune=native' was already specified in 'target' attribute
123 | __gthrw(pthread_mutex_destroy)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:123:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:125:1: error: attribute value 'tune=native' was already specified in 'target' attribute
125 | __gthrw(pthread_cond_init)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:125:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:126:1: error: attribute value 'tune=native' was already specified in 'target' attribute
126 | __gthrw(pthread_cond_broadcast)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:126:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:127:1: error: attribute value 'tune=native' was already specified in 'target' attribute
127 | __gthrw(pthread_cond_signal)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:127:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:128:1: error: attribute value 'tune=native' was already specified in 'target' attribute
128 | __gthrw(pthread_cond_wait)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:128:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:129:1: error: attribute value 'tune=native' was already specified in 'target' attribute
129 | __gthrw(pthread_cond_timedwait)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:129:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:130:1: error: attribute value 'tune=native' was already specified in 'target' attribute
130 | __gthrw(pthread_cond_destroy)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:130:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:132:1: error: attribute value 'tune=native' was already specified in 'target' attribute
132 | __gthrw(pthread_key_create)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:132:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:133:1: error: attribute value 'tune=native' was already specified in 'target' attribute
133 | __gthrw(pthread_key_delete)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:133:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:134:1: error: attribute value 'tune=native' was already specified in 'target' attribute
134 | __gthrw(pthread_mutexattr_init)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:134:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:135:1: error: attribute value 'tune=native' was already specified in 'target' attribute
135 | __gthrw(pthread_mutexattr_settype)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:135:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:136:1: error: attribute value 'tune=native' was already specified in 'target' attribute
136 | __gthrw(pthread_mutexattr_destroy)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:136:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:237:10: error: attribute value 'tune=native' was already specified in 'target' attribute
237 | __gthrw2(__gthrw_(__pthread_key_create),
| ^~~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:237:10: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/c++/10/shared_mutex:73:3: error: attribute value 'tune=native' was already specified in 'target' attribute
73 | _GLIBCXX_GTHRW(rwlock_rdlock)
| ^~~~~~~~~~~~~~
/usr/include/c++/10/shared_mutex:73:3: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/c++/10/shared_mutex:74:3: error: attribute value 'tune=native' was already specified in 'target' attribute
74 | _GLIBCXX_GTHRW(rwlock_tryrdlock)
| ^~~~~~~~~~~~~~
/usr/include/c++/10/shared_mutex:74:3: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/c++/10/shared_mutex:75:3: error: attribute value 'tune=native' was already specified in 'target' attribute
75 | _GLIBCXX_GTHRW(rwlock_wrlock)
| ^~~~~~~~~~~~~~
/usr/include/c++/10/shared_mutex:75:3: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/c++/10/shared_mutex:76:3: error: attribute value 'tune=native' was already specified in 'target' attribute
76 | _GLIBCXX_GTHRW(rwlock_trywrlock)
| ^~~~~~~~~~~~~~
/usr/include/c++/10/shared_mutex:76:3: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/c++/10/shared_mutex:77:3: error: attribute value 'tune=native' was already specified in 'target' attribute
77 | _GLIBCXX_GTHRW(rwlock_unlock)
| ^~~~~~~~~~~~~~
/usr/include/c++/10/shared_mutex:77:3: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/c++/10/shared_mutex:91:4: error: attribute value 'tune=native' was already specified in 'target' attribute
91 | __gthrw(pthread_rwlock_timedrdlock);
| ^~~~~~~
/usr/include/c++/10/shared_mutex:91:4: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/c++/10/shared_mutex:101:4: error: attribute value 'tune=native' was already specified in 'target' attribute
101 | __gthrw(pthread_rwlock_timedwrlock);
| ^~~~~~~
/usr/include/c++/10/shared_mutex:101:4: error: attribute value 'tune=native' was already specified in 'target' attribute
shortcut.cpp: In function 'long long int find_shortcut(int, std::vector<int>, std::vector<int>, int)':
shortcut.cpp:110:35: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
110 | int64_t mid = low + high >> 1;
| ~~~~^~~~~~
