// こんな僕等がお互い蹴落として
// まで掴んだ物は何ですか
// 僕は 僕を愛してあげたい
//
// こんなことなら生まれてこなけりゃって
// 全部嫌になってくけれど
// 絶えず 脈打つこれは何だろう
//
// 何だろう...
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
// Pragmas
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
// Namespaces
using namespace std;
using namespace __gnu_pbds;
// Data types
using si = short int;
using ll = long long;
using ull = unsigned long long;
using lll = __int128;
using ld = long double;
// Pairs
using pii = pair<int, int>;
using psi = pair<si, si>;
using pll = pair<ll, ll>;
using plll = pair<lll, lll>;
using pld = pair<ld, ld>;
#define fi first
#define se second
// PBDS
template<typename Z>
using ordered_set = tree<Z, null_type, less<Z>, rb_tree_tag, tree_order_statistics_node_update>;
// Various outputs and debug
template<typename Z, typename = void> struct is_iterable : false_type {};
template<typename Z> struct is_iterable<Z, void_t<decltype(begin(declval<Z>())),decltype(end(declval<Z>()))>> : true_type {};
template<typename Z> typename enable_if<is_iterable<Z>::value&&!is_same<Z, string>::value,ostream&>::type operator<<(ostream &os, const Z &v);
template<typename Y, typename Z> ostream& operator<<(ostream &os, const pair<Y, Z> &p) {
return os << "(" << p.fi << ", " << p.se << ")";
}
template<class TupType, size_t... I> void printTuple(ostream& os, const TupType& _tup, index_sequence<I...>) {
os << "(";
(..., (os << (I == 0? "" : ", ") << get<I>(_tup)));
os << ")";
}
template<class... Z> ostream& operator<<(ostream& os, const tuple<Z...>& _tup) {
printTuple(os, _tup, make_index_sequence<sizeof...(Z)>());
return os;
}
template<typename Z> typename enable_if<is_iterable<Z>::value&&!is_same<Z, string>::value,ostream&>::type operator<<(ostream &os, const Z &v) {
os << "[";
for (auto it = v.begin(); it != v.end();) { os << *it; if (++it != v.end()) os << ", "; }
return os << "]";
}
#define debug(...) logger(cout, #__VA_ARGS__, __VA_ARGS__)
#define debugV(v, x) vlogger(cout, #v, x, v[x]);
#define rrebug(...) logger(cerr, #__VA_ARGS__, __VA_ARGS__)
#define rrebugV(v, x) vlogger(cerr, #v, x, v[x]);
template <typename... Args>
void logger(ostream& os, string vars, Args &&...values) {
os << vars << " = "; string delim = "";
(..., (os << delim << values, delim = ", "));
os << "\n";
}
template<class Y, class Z>
void vlogger(ostream& os, string var, Y idx, Z val) {
os << var << "[" << idx << "] = " << val << "\n";
}
// Various macros
#define All(x) x.begin(), x.end()
#define Sort(x) sort(All(x))
#define Reverse(x) reverse(All(x))
#define Uniqueify(x) Sort(x); x.erase(unique(All(x)), x.end())
#define RandomSeed chrono::steady_clock::now().time_since_epoch().count()
#define MultipleTestcases int _tc; cin >> _tc; for (int _cur_tc = 1; _cur_tc <= _tc; _cur_tc++)
// Chmin & chmax
template<typename Z> bool chmin(Z &a, Z b) { return (b < a) ? a = b, true : false; }
template<typename Z> bool chmax(Z &a, Z b) { return (b > a) ? a = b, true : false; }
// Modular arithmetic
template<int MOD>
class ModInt {
public:
int v;
ModInt() : v(0) {}
ModInt(long long _v) {
v = int((-MOD < _v && _v < MOD) ? (_v) : (_v % MOD));
if (v < 0) v += MOD;
}
friend bool operator==(const ModInt &a, const ModInt &b) { return a.v == b.v; }
friend bool operator!=(const ModInt &a, const ModInt &b) { return a.v != b.v; }
friend bool operator< (const ModInt &a, const ModInt &b) { return a.v < b.v; }
friend bool operator<=(const ModInt &a, const ModInt &b) { return a.v <= b.v; }
friend bool operator> (const ModInt &a, const ModInt &b) { return a.v > b.v; }
friend bool operator>=(const ModInt &a, const ModInt &b) { return a.v >= b.v; }
ModInt &operator+=(const ModInt &a) { if ((v += a.v) >= MOD) v -= MOD; return *this; }
ModInt &operator-=(const ModInt &a) { if ((v -= a.v) < 0) v += MOD; return *this; }
ModInt &operator*=(const ModInt &a) { v = 1ll * v * a.v % MOD; return *this; }
ModInt &operator/=(const ModInt &a) { return (*this) *= inverse(a); }
friend ModInt pow(ModInt a, long long x) {
ModInt res = 1;
for (; x; x /= 2, a *= a) if (x & 1) res *= a;
return res;
}
friend ModInt inverse(ModInt a) { return pow(a, MOD - 2); }
ModInt operator+ () const { return ModInt( v); }
ModInt operator- () const { return ModInt(-v); }
ModInt operator++() const { return *this += 1; }
ModInt operator--() const { return *this -= 1; }
friend ModInt operator+(ModInt a, const ModInt &b) { return a += b; }
friend ModInt operator-(ModInt a, const ModInt &b) { return a -= b; }
friend ModInt operator*(ModInt a, const ModInt &b) { return a *= b; }
friend ModInt operator/(ModInt a, const ModInt &b) { return a /= b; }
friend istream &operator>>(istream &is, ModInt &v) { return is >> v.v; }
friend ostream &operator<<(ostream &os, const ModInt &v) { return os << v.v; }
};
const int ModA = 998244353;
const int ModC = 1e9 + 7;
using MintA = ModInt<ModA>;
using MintC = ModInt<ModC>;
// Other constants
const ll INF = 1e18;
const ll iINF = 1e9;
const ld EPS = 1e-9;
const ld iEPS = 1e-6;
const int maxN = 300'023;
int N, _2N;
int A[2*maxN], B[maxN], C[maxN];
vector<pii> order;
pii valid_B[2*maxN], valid_R[2*maxN];
namespace FenwickTree {
int BIT[2*maxN];
void reset() {
for (int i = 1; i <= _2N; i++) BIT[i] = 0;
}
void update(int idx, int val) {
for (; idx <= _2N; idx += (idx & -idx)) {
BIT[idx] += val;
}
}
void update(int l, int r, int val) {
if (l > r) return;
update(l, val); update(r+1, -val);
}
int query(int idx) {
if (idx > _2N) idx = _2N;
int ret = 0;
for (; idx > 0; idx -= (idx & -idx)) {
ret += BIT[idx];
}
return ret;
}
};
void work(int idx, set<int> &s, pii *valid, bool do_update) {
auto it = s.begin();
while (
!s.empty() &&
(it = s.lower_bound(idx - N + 1)) != s.end() &&
*it <= idx
) {
int t = FenwickTree::query(*it);
if (t < valid[idx].fi || t > valid[idx].se) {
s.erase(it);
} else break;
}
while (
!s.empty() &&
(it = s.upper_bound(idx)) != s.begin() &&
*(--it) >= idx - N + 1
) {
int t = FenwickTree::query(*it);
if (t < valid[idx].fi || t > valid[idx].se) {
s.erase(it);
} else break;
}
if (idx <= N) {
if (do_update) FenwickTree::update(idx + N + 1, _2N, 1);
while (
!s.empty() &&
(it = s.lower_bound(idx + N +1)) != s.end() &&
*it <= idx + _2N
) {
int t = FenwickTree::query(*it);
if (t < valid[idx].fi || t > valid[idx].se) {
s.erase(it);
} else break;
}
while (
!s.empty() &&
(it = s.upper_bound(idx + _2N)) != s.begin() &&
*(--it) >= idx + N + 1
) {
int t = FenwickTree::query(*it);
if (t < valid[idx].fi || t > valid[idx].se) {
s.erase(it);
} else break;
}
}
}
bool valid(int chk) {
for (int i = 1; i <= _2N; i++) {
valid_B[i] = {
lower_bound(B+1, B+N+1, A[i] - chk) - B,
upper_bound(B+1, B+N+1, A[i] + chk) - B - 1
};
valid_R[i] = {
lower_bound(C+1, C+N+1, A[i] - chk) - C,
upper_bound(C+1, C+N+1, A[i] + chk) - C - 1
};
}
set<int> blue, red;
for (int i = 1; i <= _2N; i++) {
blue.insert(i); red.insert(i);
}
FenwickTree::reset();
for (auto [val, idx] : order) {
FenwickTree::update(max(1, idx - N + 1), idx, 1);
work(idx, blue, valid_B, true);
work(idx, red, valid_R, false);
}
for (auto x : blue) {
if (red.count(x - N) || red.count(x + N)) return true;
}
return false;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
scanf("%d", &N);
_2N = 2*N;
for (int i = 1; i <= _2N; i++) scanf("%d", &A[i]);
for (int i = 1; i <= N; i++) scanf("%d", &B[i]);
for (int i = 1; i <= N; i++) scanf("%d", &C[i]);
for (int i = 1; i <= _2N; i++) order.push_back({A[i], i});
Sort(order); sort(B+1, B+N+1); sort(C+1, C+N+1);
int hl = 0, hr = iINF, ans = -1;
while (hl <= hr) {
int hm = (hl + hr) / 2;
if (valid(hm)) {
ans = hm;
hr = hm - 1;
} else {
hl = hm + 1;
}
}
printf("%d\n", ans);
}
// dibisakan
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:266:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
266 | scanf("%d", &N);
| ~~~~~^~~~~~~~~~
Main.cpp:269:41: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
269 | for (int i = 1; i <= _2N; i++) scanf("%d", &A[i]);
| ~~~~~^~~~~~~~~~~~~
Main.cpp:270:39: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
270 | for (int i = 1; i <= N; i++) scanf("%d", &B[i]);
| ~~~~~^~~~~~~~~~~~~
Main.cpp:271:39: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
271 | for (int i = 1; i <= N; i++) scanf("%d", &C[i]);
| ~~~~~^~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
8536 KB |
Output is correct |
2 |
Correct |
1 ms |
8540 KB |
Output is correct |
3 |
Correct |
1 ms |
8540 KB |
Output is correct |
4 |
Correct |
1 ms |
8540 KB |
Output is correct |
5 |
Correct |
1 ms |
8672 KB |
Output is correct |
6 |
Correct |
2 ms |
8540 KB |
Output is correct |
7 |
Correct |
1 ms |
8540 KB |
Output is correct |
8 |
Correct |
1 ms |
8540 KB |
Output is correct |
9 |
Correct |
1 ms |
8540 KB |
Output is correct |
10 |
Correct |
2 ms |
8536 KB |
Output is correct |
11 |
Correct |
1 ms |
8540 KB |
Output is correct |
12 |
Correct |
1 ms |
8540 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
8536 KB |
Output is correct |
2 |
Correct |
1 ms |
8540 KB |
Output is correct |
3 |
Correct |
1 ms |
8540 KB |
Output is correct |
4 |
Correct |
1 ms |
8540 KB |
Output is correct |
5 |
Correct |
1 ms |
8672 KB |
Output is correct |
6 |
Correct |
2 ms |
8540 KB |
Output is correct |
7 |
Correct |
1 ms |
8540 KB |
Output is correct |
8 |
Correct |
1 ms |
8540 KB |
Output is correct |
9 |
Correct |
1 ms |
8540 KB |
Output is correct |
10 |
Correct |
2 ms |
8536 KB |
Output is correct |
11 |
Correct |
1 ms |
8540 KB |
Output is correct |
12 |
Correct |
1 ms |
8540 KB |
Output is correct |
13 |
Correct |
1 ms |
8536 KB |
Output is correct |
14 |
Correct |
1 ms |
8540 KB |
Output is correct |
15 |
Correct |
1 ms |
8668 KB |
Output is correct |
16 |
Correct |
1 ms |
8540 KB |
Output is correct |
17 |
Correct |
1 ms |
8540 KB |
Output is correct |
18 |
Correct |
1 ms |
8540 KB |
Output is correct |
19 |
Correct |
1 ms |
8540 KB |
Output is correct |
20 |
Correct |
1 ms |
8540 KB |
Output is correct |
21 |
Correct |
1 ms |
8540 KB |
Output is correct |
22 |
Correct |
1 ms |
8540 KB |
Output is correct |
23 |
Correct |
1 ms |
8540 KB |
Output is correct |
24 |
Correct |
1 ms |
8540 KB |
Output is correct |
25 |
Correct |
1 ms |
8540 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
8536 KB |
Output is correct |
2 |
Correct |
1 ms |
8540 KB |
Output is correct |
3 |
Correct |
1 ms |
8540 KB |
Output is correct |
4 |
Correct |
1 ms |
8540 KB |
Output is correct |
5 |
Correct |
1 ms |
8672 KB |
Output is correct |
6 |
Correct |
2 ms |
8540 KB |
Output is correct |
7 |
Correct |
1 ms |
8540 KB |
Output is correct |
8 |
Correct |
1 ms |
8540 KB |
Output is correct |
9 |
Correct |
1 ms |
8540 KB |
Output is correct |
10 |
Correct |
2 ms |
8536 KB |
Output is correct |
11 |
Correct |
1 ms |
8540 KB |
Output is correct |
12 |
Correct |
1 ms |
8540 KB |
Output is correct |
13 |
Correct |
1 ms |
8536 KB |
Output is correct |
14 |
Correct |
1 ms |
8540 KB |
Output is correct |
15 |
Correct |
1 ms |
8668 KB |
Output is correct |
16 |
Correct |
1 ms |
8540 KB |
Output is correct |
17 |
Correct |
1 ms |
8540 KB |
Output is correct |
18 |
Correct |
1 ms |
8540 KB |
Output is correct |
19 |
Correct |
1 ms |
8540 KB |
Output is correct |
20 |
Correct |
1 ms |
8540 KB |
Output is correct |
21 |
Correct |
1 ms |
8540 KB |
Output is correct |
22 |
Correct |
1 ms |
8540 KB |
Output is correct |
23 |
Correct |
1 ms |
8540 KB |
Output is correct |
24 |
Correct |
1 ms |
8540 KB |
Output is correct |
25 |
Correct |
1 ms |
8540 KB |
Output is correct |
26 |
Correct |
66 ms |
9152 KB |
Output is correct |
27 |
Correct |
64 ms |
9052 KB |
Output is correct |
28 |
Correct |
57 ms |
9052 KB |
Output is correct |
29 |
Correct |
2 ms |
8540 KB |
Output is correct |
30 |
Correct |
49 ms |
9052 KB |
Output is correct |
31 |
Correct |
55 ms |
9048 KB |
Output is correct |
32 |
Correct |
25 ms |
8796 KB |
Output is correct |
33 |
Correct |
12 ms |
8536 KB |
Output is correct |
34 |
Correct |
56 ms |
9052 KB |
Output is correct |
35 |
Correct |
58 ms |
9052 KB |
Output is correct |
36 |
Correct |
48 ms |
9052 KB |
Output is correct |
37 |
Correct |
44 ms |
9052 KB |
Output is correct |
38 |
Correct |
47 ms |
9052 KB |
Output is correct |
39 |
Correct |
51 ms |
9048 KB |
Output is correct |
40 |
Correct |
55 ms |
9120 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
5049 ms |
79876 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
8536 KB |
Output is correct |
2 |
Correct |
1 ms |
8540 KB |
Output is correct |
3 |
Correct |
1 ms |
8540 KB |
Output is correct |
4 |
Correct |
1 ms |
8540 KB |
Output is correct |
5 |
Correct |
1 ms |
8672 KB |
Output is correct |
6 |
Correct |
2 ms |
8540 KB |
Output is correct |
7 |
Correct |
1 ms |
8540 KB |
Output is correct |
8 |
Correct |
1 ms |
8540 KB |
Output is correct |
9 |
Correct |
1 ms |
8540 KB |
Output is correct |
10 |
Correct |
2 ms |
8536 KB |
Output is correct |
11 |
Correct |
1 ms |
8540 KB |
Output is correct |
12 |
Correct |
1 ms |
8540 KB |
Output is correct |
13 |
Correct |
1 ms |
8536 KB |
Output is correct |
14 |
Correct |
1 ms |
8540 KB |
Output is correct |
15 |
Correct |
1 ms |
8668 KB |
Output is correct |
16 |
Correct |
1 ms |
8540 KB |
Output is correct |
17 |
Correct |
1 ms |
8540 KB |
Output is correct |
18 |
Correct |
1 ms |
8540 KB |
Output is correct |
19 |
Correct |
1 ms |
8540 KB |
Output is correct |
20 |
Correct |
1 ms |
8540 KB |
Output is correct |
21 |
Correct |
1 ms |
8540 KB |
Output is correct |
22 |
Correct |
1 ms |
8540 KB |
Output is correct |
23 |
Correct |
1 ms |
8540 KB |
Output is correct |
24 |
Correct |
1 ms |
8540 KB |
Output is correct |
25 |
Correct |
1 ms |
8540 KB |
Output is correct |
26 |
Correct |
66 ms |
9152 KB |
Output is correct |
27 |
Correct |
64 ms |
9052 KB |
Output is correct |
28 |
Correct |
57 ms |
9052 KB |
Output is correct |
29 |
Correct |
2 ms |
8540 KB |
Output is correct |
30 |
Correct |
49 ms |
9052 KB |
Output is correct |
31 |
Correct |
55 ms |
9048 KB |
Output is correct |
32 |
Correct |
25 ms |
8796 KB |
Output is correct |
33 |
Correct |
12 ms |
8536 KB |
Output is correct |
34 |
Correct |
56 ms |
9052 KB |
Output is correct |
35 |
Correct |
58 ms |
9052 KB |
Output is correct |
36 |
Correct |
48 ms |
9052 KB |
Output is correct |
37 |
Correct |
44 ms |
9052 KB |
Output is correct |
38 |
Correct |
47 ms |
9052 KB |
Output is correct |
39 |
Correct |
51 ms |
9048 KB |
Output is correct |
40 |
Correct |
55 ms |
9120 KB |
Output is correct |
41 |
Execution timed out |
5049 ms |
79876 KB |
Time limit exceeded |
42 |
Halted |
0 ms |
0 KB |
- |