結果

問題 No.3436 [Cherry 8th Tune B] この夏に何が起こるかな?
コンテスト
ユーザー zawakasu
提出日時 2026-01-23 22:03:53
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 563 ms / 4,000 ms
コード長 5,591 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,445 ms
コンパイル使用メモリ 259,196 KB
実行使用メモリ 23,512 KB
最終ジャッジ日時 2026-01-23 22:06:18
合計ジャッジ時間 22,995 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 43
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <iomanip>
#include <cassert>
#include <vector>
#include <algorithm>
#include <utility>
#include <numeric>
#include <tuple>
#include <ranges>
#include <random>
// #include "Src/Number/IntegerDivision.hpp"


#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa

#include <cmath>
#include <functional>
#include <type_traits>

namespace zawa {

namespace internal {

template <class T>
T MidPoint(T a, T b) {
    if (a > b) std::swap(a, b);
    return a + ((b - a) >> 1);
}

template <class T>
T Abs(T a, T b) {
    return (a >= b ? a - b : b - a);
}

} // namespace zawa::internal

template <class T, class Function>
T BinarySearch(T ok, T ng, const Function& f) {
    static_assert(std::is_integral_v<T>, "T must be integral type");
    static_assert(std::is_convertible_v<Function, std::function<bool(T)>>, "f must be function bool(T)");
    while (internal::Abs(ok, ng) > 1) {
        T mid{ internal::MidPoint(ok, ng) };
        (f(mid) ? ok : ng) = mid;
    }
    return ok;
}

template <class T, class Function>
T BinarySearch(T ok, T ng, const Function& f, u32 upperLimit) {
    static_assert(std::is_signed_v<T>, "T must be signed arithmetic type");
    static_assert(std::is_convertible_v<Function, std::function<bool(T)>>, "f must be function bool(T)");
    for (u32 _{} ; _ < upperLimit ; _++) {
        T mid{ (ok + ng) / (T)2 };
        (f(mid) ? ok : ng) = mid;
    }
    return ok;
}

} // namespace zawa
// #include "Src/Sequence/CompressedSequence.hpp"
// #include "Src/Sequence/RunLengthEncoding.hpp"
// #include "Src/Algebra/Group/AdditiveGroup.hpp"
// #include "Src/DataStructure/FenwickTree/FenwickTree.hpp"
// #include "Src/DataStructure/SegmentTree/SegmentTree.hpp"
// #include "Src/DataStructure/DisjointSetUnion/DisjointSetUnion.hpp"
// #include "Src/DataStructure/Heap/BinaryHeap.hpp"
namespace zawa {}
using namespace zawa;
// #include "atcoder/modint"
// using mint = atcoder::modint998244353;
// #include <array>
// #include <bit>
// #include <bitset>
// #include <climits>
// #include <cmath>
#include <set>
// #include <unordered_set>
// #include <map>
// #include <unordered_map>
// #include <optional>
// #include <queue>
// #include <stack>
// #include <deque>
// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
using namespace std;
template <class T, class U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
    os << '(' << p.first << ',' << p.second << ')';
    return os;
}
template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    for (int i = 0 ; i < ssize(v) ; i++)
        os << v[i] << (i + 1 == ssize(v) ? "" : " ");
    return os;
}
void solve() {
    int N, M, K;
    long long P;
    cin >> N >> M >> K >> P;
    vector<long long> T(N), B(M), S(K);
    vector<int> C(N), D(M);
    for (auto& x : T)
        cin >> x;
    for (auto& x : C) {
        cin >> x;
        x--;
    }
    for (auto& x : B)
        cin >> x;
    for (auto& x : D) {
        cin >> x;
        x--;
    }
    for (auto& x : S)
        cin >> x;
    vector<long long> all = B;
    ranges::sort(all);
    vector<vector<pair<long long,int>>> bottoms(K);
    for (int i = 0 ; i < M ; i++) 
        bottoms[D[i]].push_back({B[i],i});
    for (int i = 0 ; i < K ; i++)
        ranges::sort(bottoms[i]);
    auto f = [&](long long val) -> bool {
        long long cnt = 0;
        for (int i = 0 ; i < N ; i++) {
            int other = [&]() {
                int res = ranges::upper_bound(all, val - T[i]) - all.begin();
                res -= ranges::upper_bound(bottoms[C[i]], pair{val - T[i]+1,-1}) - bottoms[C[i]].begin();
                return res;
            }();
            int same = ranges::upper_bound(bottoms[C[i]], pair{val + S[C[i]] - T[i]+1,-1}) - bottoms[C[i]].begin();
            cnt += other + same;
        }
        return cnt >= P;
    };
    set<pair<long long,int>> mpAll;
    vector<set<pair<long long,int>>> mp(K);
    for (int i = 0 ; i < M ; i++) {
        mpAll.insert({B[i],i});
        mp[D[i]].insert({B[i], i});
    }
    long long price = BinarySearch((long long)3e9, 0LL, f);
    for (int i = 0 ; i < N ; i++) {
        if (auto it = mp[C[i]].lower_bound(pair{price + S[C[i]] - T[i], -1}) ; it != mp[C[i]].end() and it->first == price + S[C[i]] - T[i]) {
            cout << i + 1 << ' ' << it->second + 1 << '\n';
            return;
        }
        for (auto p : bottoms[C[i]])
            mpAll.erase(mpAll.find(p));
        if (auto it = mpAll.lower_bound(pair{price - T[i], -1}) ; it != mpAll.end() and it->first == price - T[i]) {
            cout << i + 1 << ' ' << it->second + 1 << '\n';
            return;
        }
        for (auto p : bottoms[C[i]])
            mpAll.insert(p);
    }
}
int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(20);
#if !defined DEBUG
    int T;
    cin >> T;
    while (T--)
        solve();
#else
    mt19937 mt{random_device{}()};
    for (int testcase = 0 ; ; ) {
        cerr << "----------" << ++testcase << "----------" << endl;
        
        auto a = solve(), b = naive();
        if (a != b) {
            // print testcase

            cerr << "you: " << a << endl;
            cout << "correct: " << b << endl;
            exit(0);
        }
    }
#endif
}
0