結果

問題 No.3436 [Cherry 8th Tune B] この夏に何が起こるかな?
コンテスト
ユーザー SnowBeenDiding
提出日時 2026-01-29 10:18:05
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
TLE  
実行時間 -
コード長 10,152 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 12,030 ms
コンパイル使用メモリ 437,856 KB
実行使用メモリ 62,240 KB
最終ジャッジ日時 2026-01-29 10:19:04
合計ジャッジ時間 55,536 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 10 TLE * 1 -- * 32
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘void solve()’:
main.cpp:335:46: 警告: ‘tmpe’ may be used uninitialized [-Wmaybe-uninitialized]
  335 |     rep(i, 0, n) if (a[i] == tmpx && b[i] == tmpe) ansi = i;
      |                                              ^~~~
main.cpp:302:9: 備考: ‘tmpe’ はここで定義されています
  302 |     int tmpe, tmpx;
      |         ^~~~
main.cpp:337:18: 警告: ‘tmpx’ may be used uninitialized [-Wmaybe-uninitialized]
  337 |         ll val = tmpx + c[j];
      |                  ^~~~
main.cpp:302:15: 備考: ‘tmpx’ はここで定義されています
  302 |     int tmpe, tmpx;
      |               ^~~~
main.cpp:341:20: 警告: ‘ansi’ may be used uninitialized [-Wmaybe-uninitialized]
  341 |     cout << ansi + 1 << ' ' << ansj + 1 << '\n';
      |                    ^
main.cpp:334:9: 備考: ‘ansi’ はここで定義されています
  334 |     int ansi, ansj;
      |         ^~~~
main.cpp:341:39: 警告: ‘ansj’ may be used uninitialized [-Wmaybe-uninitialized]
  341 |     cout << ansi + 1 << ' ' << ansj + 1 << '\n';
      |                                       ^
main.cpp:334:15: 備考: ‘ansj’ はここで定義されています
  334 |     int ansi, ansj;
      |               ^~~~

ソースコード

diff #
raw source code 

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>

#include <atcoder/all>
#define rep(i, a, b) for (ll i = (ll)(a); i < (ll)(b); i++)
using namespace atcoder;
using namespace std;

typedef long long ll;

template <class S, S (*op)(S, S), S (*e)()>
class super_dynamic_segtree {
   public:
    using i64 = std::int64_t;

    // 初期範囲 [0,1)
    super_dynamic_segtree() : lo_(0), hi_(1), root_(nullptr) {}

    // 初期範囲を指定（lo < hi 必須）。内部では幅を2冪に切り上げつつ包含。
    super_dynamic_segtree(i64 lo, i64 hi) : root_(nullptr) {
        assert(lo < hi);
        i64 w = hi - lo;

        i64 pw = 1;
        while (pw < w) {
            if (pw > (std::numeric_limits<i64>::max() / 2)) {
                assert(false && "initial range too large");
            }
            pw <<= 1;
        }
        lo_ = lo;
        hi_ = lo_ + pw;

        // 念のため：元のhiまで含むように（端の計算誤差対策）
        while (hi_ < hi) expand_right_();
    }

    // 現在カバーしている範囲 [lo_, hi_)
    std::pair<i64, i64> bounds() const { return {lo_, hi_}; }

    // 点更新（必要なら拡張）
    void set(i64 p, S x) {
        ensure_point(p);
        set(root_, lo_, hi_, p, x);
    }

    // 点取得（範囲外は e()。拡張しない）
    S get(i64 p) const {
        if (p < lo_ || hi_ <= p) return e();
        return get(root_, lo_, hi_, p);
    }

    // 区間積 [l, r)（範囲外は e() として扱う。拡張しない）
    S prod(i64 l, i64 r) const {
        assert(l <= r);
        if (l == r) return e();
        return prod(root_, lo_, hi_, l, r);
    }

    S all_prod() const { return root_ ? root_->prod : e(); }

    // 区間リセット [l, r)（範囲外は無視。拡張しない）
    void reset(i64 l, i64 r) {
        assert(l <= r);
        if (l == r) return;
        reset(root_, lo_, hi_, l, r);
    }

    // 必要なら明示的に点が入るまで拡張（max_right/min_leftの探索範囲確保にも）
    void ensure_point(i64 p) {
        while (p < lo_ || hi_ <= p) {
            if (p < lo_)
                expand_left_();
            else
                expand_right_();
        }
    }

    // [l, r) を包含するまで拡張
    void ensure_range(i64 l, i64 r) {
        assert(l < r);
        ensure_point(l);
        ensure_point(r - 1);
    }

    // max_right / min_left は「現在のbounds内」で探索（ACLと同様に f(e())==true
    // 前提）
    template <class F>
    i64 max_right(i64 l, const F& f) const {
        assert(f(e()));
        if (l <= lo_) l = lo_;
        if (l >= hi_) return hi_;

        S acc = e();
        return max_right(root_, lo_, hi_, l, f, acc);
    }

    template <class F>
    i64 min_left(i64 r, const F& f) const {
        assert(f(e()));
        if (r >= hi_) r = hi_;
        if (r <= lo_) return lo_;

        S acc = e();
        return min_left(root_, lo_, hi_, r, f, acc);
    }

   private:
    struct node;
    using node_ptr = std::unique_ptr<node>;

    struct node {
        S prod;
        node_ptr left;
        node_ptr right;
        node() : prod(e()), left(nullptr), right(nullptr) {}
    };

    i64 lo_, hi_;  // カバー区間 [lo_, hi_) 幅は2冪
    node_ptr root_;

    static i64 mid(i64 a, i64 b) {
        // オーバーフロー回避：a + (b-a)/2
        return a + (b - a) / 2;
    }

    // 右へ倍拡張： [lo, hi) -> [lo, hi + width)
    void expand_right_() {
        i64 w = hi_ - lo_;
        assert(w > 0);
        if (hi_ > std::numeric_limits<i64>::max() - w) {
            assert(false && "range expansion overflow (right)");
        }
        node_ptr new_root = std::make_unique<node>();
        // 古い区間は新しい区間の「左半分」
        new_root->left = std::move(root_);
        pull(new_root);
        root_ = std::move(new_root);
        hi_ += w;
    }

    // 左へ倍拡張： [lo, hi) -> [lo - width, hi)
    void expand_left_() {
        i64 w = hi_ - lo_;
        assert(w > 0);
        if (lo_ < std::numeric_limits<i64>::min() + w) {
            assert(false && "range expansion overflow (left)");
        }
        node_ptr new_root = std::make_unique<node>();
        // 古い区間は新しい区間の「右半分」
        new_root->right = std::move(root_);
        pull(new_root);
        root_ = std::move(new_root);
        lo_ -= w;
    }

    static S prod_of(const node_ptr& t) { return t ? t->prod : e(); }

    static void pull(node_ptr& t) {
        if (!t) return;
        t->prod = op(prod_of(t->left), prod_of(t->right));
    }

    static void set(node_ptr& t, i64 a, i64 b, i64 p, S x) {
        if (!t) t = std::make_unique<node>();
        if (b - a == 1) {
            t->prod = x;
            return;
        }
        i64 c = mid(a, b);
        if (p < c)
            set(t->left, a, c, p, x);
        else
            set(t->right, c, b, p, x);
        pull(t);
    }

    static S get(const node_ptr& t, i64 a, i64 b, i64 p) {
        if (!t) return e();
        if (b - a == 1) return t->prod;
        i64 c = mid(a, b);
        if (p < c)
            return get(t->left, a, c, p);
        else
            return get(t->right, c, b, p);
    }

    static S prod(const node_ptr& t, i64 a, i64 b, i64 l, i64 r) {
        if (!t || r <= a || b <= l) return e();
        if (l <= a && b <= r) return t->prod;
        i64 c = mid(a, b);
        return op(prod(t->left, a, c, l, r), prod(t->right, c, b, l, r));
    }

    static void reset(node_ptr& t, i64 a, i64 b, i64 l, i64 r) {
        if (!t || r <= a || b <= l) return;
        if (l <= a && b <= r) {
            t.reset();
            return;
        }
        if (b - a == 1) {
            t.reset();
            return;
        }
        i64 c = mid(a, b);
        reset(t->left, a, c, l, r);
        reset(t->right, c, b, l, r);
        if (!t->left && !t->right) {
            t.reset();
            return;
        }
        pull(t);
    }

    template <class F>
    static i64 max_right(const node_ptr& t, i64 a, i64 b, i64 l, const F& f,
                         S& acc) {
        if (b <= l) return b;  // この区間全体が探索対象外（左側）
        if (!t) {
            // 全部単位元。accと合成して条件OKなら区間末端まで行ける
            S nxt = op(acc, e());
            (void)nxt;
            return b;  // ここは「値が全てe()」なので、fが成り立つ限り右へ進める扱い
        }
        if (l <= a) {
            S nxt = op(acc, t->prod);
            if (f(nxt)) {
                acc = nxt;
                return b;
            }
            if (b - a == 1) return a;  // ここで壊れる => この点
        }
        if (b - a == 1) return b;  // l > a で葉なら通過
        i64 c = mid(a, b);
        i64 res = max_right(t->left, a, c, l, f, acc);
        if (res != c) return res;
        return max_right(t->right, c, b, l, f, acc);
    }

    template <class F>
    static i64 min_left(const node_ptr& t, i64 a, i64 b, i64 r, const F& f,
                        S& acc) {
        if (r <= a) return a;  // この区間全体が探索対象外（右側）
        if (!t) {
            // 全部単位元
            S nxt = op(e(), acc);
            (void)nxt;
            return a;
        }
        if (b <= r) {
            S nxt = op(t->prod, acc);
            if (f(nxt)) {
                acc = nxt;
                return a;
            }
            if (b - a == 1) return b;  // ここで壊れる => a+1 を返す形に相当
        }
        if (b - a == 1) return a;
        i64 c = mid(a, b);
        i64 res = min_left(t->right, c, b, r, f, acc);
        if (res != c) return res;
        return min_left(t->left, a, c, r, f, acc);
    }
};

void solve() {
    super_dynamic_segtree<ll, [](const ll a, const ll b) { return a + b; },
                          [] { return 0LL; }>
        st;
    auto add = [&](ll val, ll x) { st.set(val, st.prod(val, val + 1) + x); };

    ll n, m, k, p;
    cin >> n >> m >> k >> p;
    vector<vector<ll>> A(k), B(k);
    vector<ll> a(n), b(n), c(m), d(m);
    rep(i, 0, n) cin >> a[i];
    rep(i, 0, n) cin >> b[i], b[i]--;
    rep(i, 0, m) cin >> c[i];
    rep(i, 0, m) cin >> d[i], d[i]--;
    rep(i, 0, n) A[b[i]].emplace_back(a[i]);
    rep(i, 0, m) B[d[i]].emplace_back(c[i]);
    rep(i, 0, m) add(c[i], 1);
    vector<ll> e(k);
    rep(i, 0, k) cin >> e[i];
    int ce = -1;
    auto change_e = [&](int ne) {
        if (ne == ce) return;
        if (ce != -1) {
            for (auto x : B[ce]) {
                add(x - e[ce], -1);
                add(x, +1);
            }
        }
        for (auto x : B[ne]) {
            add(x, -1);
            add(x - e[ne], +1);
        }
        ce = ne;
    };
    int tmpe, tmpx;
    auto check = [&](ll mid, bool set_ans = false) {
        ll sm = 0;
        rep(i, 0, k) {
            if (A[i].empty()) continue;
            change_e(i);
            for (auto x : A[i]) {
                sm += st.prod(-3e9, mid - x + 1);
                if (set_ans) {
                    if (st.prod(mid - x, mid - x + 1)) {
                        tmpe = i;
                        tmpx = x;
                    }
                }
            }
        }
        return sm >= p;
    };
    auto binary = [&]() {
        ll wa = -1, ac = 3e9;
        while (llabs(ac - wa) > 1) {
            ll mid = ac + (wa - ac) / 2;
            if (check(mid)) {
                ac = mid;
            } else {
                wa = mid;
            }
        }
        return ac;
    };
    ll tar = binary();
    check(tar, true);
    int ansi, ansj;
    rep(i, 0, n) if (a[i] == tmpx && b[i] == tmpe) ansi = i;
    rep(j, 0, m) {
        ll val = tmpx + c[j];
        if (d[j] == tmpe) val -= e[tmpe];
        if (tar == val) ansj = j;
    }
    cout << ansi + 1 << ' ' << ansj + 1 << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);
    int t;
    cin >> t;
    while (t--) solve();
}
0