結果

問題 No.3436 [Cherry 8th Tune B] この夏に何が起こるかな?
コンテスト
ユーザー SnowBeenDiding
提出日時 2026-01-29 10:42:17
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
TLE  
実行時間 -
コード長 8,649 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 7,946 ms
コンパイル使用メモリ 390,084 KB
実行使用メモリ 61,732 KB
最終ジャッジ日時 2026-01-29 10:43:12
合計ジャッジ時間 47,870 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 10 TLE * 3 -- * 30
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘void solve()’:
main.cpp:312:9: 警告: ‘ansi’ may be used uninitialized [-Wmaybe-uninitialized]
  312 |     int ansi, ansj;
      |         ^~~~
main.cpp:279:9: 警告: ‘tmpe’ may be used uninitialized [-Wmaybe-uninitialized]
  279 |     int tmpe, tmpx;
      |         ^~~~
main.cpp:279:15: 警告: ‘tmpx’ may be used uninitialized [-Wmaybe-uninitialized]
  279 |     int tmpe, tmpx;
      |               ^~~~
main.cpp:319:39: 警告: ‘ansj’ may be used uninitialized [-Wmaybe-uninitialized]
  319 |     cout << ansi + 1 << ' ' << ansj + 1 << '\n';
      |                                       ^
main.cpp:312:15: 備考: ‘ansj’ はここで定義されています
  312 |     int ansi, ansj;
      |               ^~~~

ソースコード

diff #
raw source code 

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

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

void solve() {
    super_dynamic_segtree<int, [](const int a, const int b) { return a + b; },
                          [] { return 0; }>
        st;
    auto add = [&](ll val, int x) { st.set(val, st.prod(val, val + 1) + 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(-3e9, mid - x + 1);
                if (set_ans) {
                    if (st.prod(mid - x, mid - x + 1)) {
                        tmpe = i;
                        tmpx = x;
                    }
                }
            }
        }
        return sm >= p;
    };
    auto binary = [&]() {
        int wa = -1, 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();
}
0