Submission #1074428

#	Time	Username	Problem	Language	Result	Execution time	Memory
1074428		Zanite	Growing Vegetables is Fun 5 (JOI24_vegetables5)	C++17	30 / 100	5049 ms	79876 KiB

Main

// こんな僕等がお互い蹴落として
// まで掴んだ物は何ですか
// 僕は　僕を愛してあげたい
// 
// こんなことなら生まれてこなけりゃって
// 全部嫌になってくけれど
// 絶えず　脈打つこれは何だろう
// 
// 何だろう...

#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 (stderr)

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]);
      |                                  ~~~~~^~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 21 / 21
• Subtask 4: 0 / 37
• Subtask 5: 0 / 33