#1146165 (C++23) No.3436 [Cherry 8th Tune B] この夏に何が起こるかな?

• 問題: No.3436 [Cherry 8th Tune B] この夏に何が起こるかな?
• ユーザー: SnowBeenDiding
• 提出日時: 2026-01-29 10:57:34
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 3,420 ms / 4,000 ms
• コード長: 13,510 bytes
• コンパイル時間: 8,286 ms
• コンパイル使用メモリ: 391,500 KB
• 実行使用メモリ: 17,020 KB
• 最終ジャッジ日時: 2026-01-29 10:58:47
• 合計ジャッジ時間: 63,736 ms
• ジャッジサーバーID （参考情報）: judge2 / judge4

ファイルパターン	結果
sample	AC * 1
other	AC * 43

コンパイルメッセージ

main.cpp: In function ‘void solve()’:
main.cpp:483:9: 警告: ‘ansi’ may be used uninitialized [-Wmaybe-uninitialized]
  483 |     int ansi, ansj;
      |         ^~~~
main.cpp:450:9: 警告: ‘tmpe’ may be used uninitialized [-Wmaybe-uninitialized]
  450 |     int tmpe, tmpx;
      |         ^~~~
main.cpp:450:15: 警告: ‘tmpx’ may be used uninitialized [-Wmaybe-uninitialized]
  450 |     int tmpe, tmpx;
      |               ^~~~
main.cpp:490:39: 警告: ‘ansj’ may be used uninitialized [-Wmaybe-uninitialized]
  490 |     cout << ansi + 1 << ' ' << ansj + 1 << '\n';
      |                                       ^
main.cpp:483:15: 備考: ‘ansj’ はここで定義されています
  483 |     int ansi, ansj;
      |               ^~~~

ソースコード

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

#define rep(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
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;

    super_dynamic_segtree() : lo_(0), hi_(1), root_(nullptr) {}

    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;
        while (hi_ < hi) expand_right_();
    }

    std::pair<i64, i64> bounds() const { return {lo_, hi_}; }

    void set(i64 p, S x) {
        ensure_point(p);
        set(root_, lo_, hi_, p, x);
    }

    S get(i64 p) const {
        if (p < lo_ || hi_ <= p) return e();
        return get(root_, lo_, hi_, p);
    }

    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(); }

    void reset(i64 l, i64 r) {
        assert(l <= r);
        if (l == r) return;
        reset(root_, lo_, hi_, l, r);
    }

    void ensure_point(i64 p) {
        while (p < lo_ || hi_ <= p) {
            if (p < lo_)
                expand_left_();
            else
                expand_right_();
        }
    }

    void ensure_range(i64 l, i64 r) {
        assert(l < r);
        ensure_point(l);
        ensure_point(r - 1);
    }

    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_;
    node_ptr root_;

    static i64 mid(i64 a, i64 b) { return a + (b - a) / 2; }

    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;
    }

    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) {
            S nxt = op(acc, e());
            (void)nxt;
            return b;
        }
        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;
        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;
        }
        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);
    }
};

template <class S, S (*op)(S, S), S (*e)()>
class dynamic_segtree {
    // https://atcoder.jp/contests/abc403/submissions/66024391
   public:
    dynamic_segtree(size_t n) : n(n), root(nullptr) {}

    void set(size_t p, S x) {
        assert(p < n);
        set(root, 0, n, p, x);
    }

    S get(size_t p) const {
        assert(p < n);
        return get(root, 0, n, p);
    }

    S prod(size_t l, size_t r) const {
        assert(l <= r && r <= n);
        return prod(root, 0, n, l, r);
    }

    S all_prod() const { return root ? root->product : e(); }

    void reset(size_t l, size_t r) {
        assert(l <= r && r <= n);
        return reset(root, 0, n, l, r);
    }

    template <bool (*f)(S)>
    size_t max_right(size_t l) const {
        return max_right(l, [](S x) { return f(x); });
    }

    template <class F>
    size_t max_right(size_t l, const F& f) const {
        assert(l <= n);
        S product = e();
        assert(f(product));
        return max_right(root, 0, n, l, f, product);
    }

    template <bool (*f)(S)>
    size_t min_left(size_t r) const {
        return min_left(r, [](S x) { return f(x); });
    }

    template <class F>
    size_t min_left(size_t r, const F& f) const {
        assert(r <= n);
        S product = e();
        assert(f(product));
        return min_left(root, 0, n, r, f, product);
    }

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

    struct node {
        size_t index;
        S value, product;
        node_ptr left, right;

        node(size_t index, S value)
            : index(index),
              value(value),
              product(value),
              left(nullptr),
              right(nullptr) {}

        void update() {
            product = op(op(left ? left->product : e(), value),
                         right ? right->product : e());
        }
    };

    const size_t n;
    node_ptr root;

    void set(node_ptr& t, size_t a, size_t b, size_t p, S x) const {
        if (!t) {
            t = std::make_unique<node>(p, x);
            return;
        }
        if (t->index == p) {
            t->value = x;
            t->update();
            return;
        }
        size_t c = (a + b) >> 1;
        if (p < c) {
            if (t->index < p) std::swap(t->index, p), std::swap(t->value, x);
            set(t->left, a, c, p, x);
        } else {
            if (p < t->index) std::swap(p, t->index), std::swap(x, t->value);
            set(t->right, c, b, p, x);
        }
        t->update();
    }

    S get(const node_ptr& t, size_t a, size_t b, size_t p) const {
        if (!t) return e();
        if (t->index == p) return t->value;
        size_t c = (a + b) >> 1;
        if (p < c)
            return get(t->left, a, c, p);
        else
            return get(t->right, c, b, p);
    }

    S prod(const node_ptr& t, size_t a, size_t b, size_t l, size_t r) const {
        if (!t || b <= l || r <= a) return e();
        if (l <= a && b <= r) return t->product;
        size_t c = (a + b) >> 1;
        S result = prod(t->left, a, c, l, r);
        if (l <= t->index && t->index < r) result = op(result, t->value);
        return op(result, prod(t->right, c, b, l, r));
    }

    void reset(node_ptr& t, size_t a, size_t b, size_t l, size_t r) const {
        if (!t || b <= l || r <= a) return;
        if (l <= a && b <= r) {
            t.reset();
            return;
        }
        size_t c = (a + b) >> 1;
        reset(t->left, a, c, l, r);
        reset(t->right, c, b, l, r);
        t->update();
    }

    template <class F>
    size_t max_right(const node_ptr& t, size_t a, size_t b, size_t l,
                     const F& f, S& product) const {
        if (!t || b <= l) return n;
        if (f(op(product, t->product))) {
            product = op(product, t->product);
            return n;
        }
        size_t c = (a + b) >> 1;
        size_t result = max_right(t->left, a, c, l, f, product);
        if (result != n) return result;
        if (l <= t->index) {
            product = op(product, t->value);
            if (!f(product)) return t->index;
        }
        return max_right(t->right, c, b, l, f, product);
    }

    template <class F>
    size_t min_left(const node_ptr& t, size_t a, size_t b, size_t r, const F& f,
                    S& product) const {
        if (!t || r <= a) return 0;
        if (f(op(t->product, product))) {
            product = op(t->product, product);
            return 0;
        }
        size_t c = (a + b) >> 1;
        size_t result = min_left(t->right, c, b, r, f, product);
        if (result != 0) return result;
        if (t->index < r) {
            product = op(t->value, product);
            if (!f(product)) return t->index + 1;
        }
        return min_left(t->left, a, c, r, f, product);
    }
};

void solve() {
    dynamic_segtree<int, [](const int a, const int b) { return a + b; },
                    [] { return 0; }>
        st(6e9);
    const ll geta = 3e9;
    auto add = [&](int val, int x) {
        st.set(val + geta, st.get(val + geta) + x);
    };
    int n, m, k;
    ll p;
    cin >> n >> m >> k >> p;
    vector<vector<int>> A(k), B(k);
    vector<int> 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<int> 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 = [&](int 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]) {
                if (-3e9 > mid - x + 1) continue;
                sm += st.prod(0, mid - x + 1 + geta);
                if (set_ans) {
                    if (st.get(mid - x + geta)) {
                        tmpe = i;
                        tmpx = x;
                    }
                }
            }
        }
        return sm >= p;
    };
    auto binary = [&]() {
        int wa = 0, ac = 2e9 + 10;
        while (llabs(ac - wa) > 1) {
            int mid = ac + (wa - ac) / 2;
            if (check(mid)) {
                ac = mid;
            } else {
                wa = mid;
            }
        }
        return ac;
    };
    int 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) {
        int 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();
}