#681031 (C++14) No.1597 Matrix Sort

• 問題: No.1597 Matrix Sort
• ユーザー: qqq xxa
• 提出日時: 2021-07-22 17:30:45
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 410 ms / 1,500 ms
• コード長: 1,140 bytes
• コンパイル時間: 1,746 ms
• コンパイル使用メモリ: 174,444 KB
• 実行使用メモリ: 6,948 KB
• 最終ジャッジ日時: 2024-07-17 14:58:58
• 合計ジャッジ時間: 10,130 ms
• ジャッジサーバーID （参考情報）: judge3 / judge5

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 6,812 KB
testcase_01	AC	2 ms; 6,940 KB
testcase_02	AC	2 ms; 6,944 KB
testcase_03	AC	369 ms; 6,944 KB
testcase_04	AC	388 ms; 6,944 KB
testcase_05	AC	407 ms; 6,940 KB
testcase_06	AC	397 ms; 6,940 KB
testcase_07	AC	410 ms; 6,940 KB
testcase_08	AC	324 ms; 6,940 KB
testcase_09	AC	339 ms; 6,940 KB
testcase_10	AC	234 ms; 6,940 KB
testcase_11	AC	205 ms; 6,948 KB
testcase_12	AC	178 ms; 6,940 KB
testcase_13	AC	308 ms; 6,944 KB
testcase_14	AC	349 ms; 6,940 KB
testcase_15	AC	146 ms; 6,940 KB
testcase_16	AC	216 ms; 6,944 KB
testcase_17	AC	246 ms; 6,940 KB
testcase_18	AC	374 ms; 6,944 KB
testcase_19	AC	283 ms; 6,940 KB
testcase_20	AC	240 ms; 6,940 KB
testcase_21	AC	233 ms; 6,940 KB
testcase_22	AC	236 ms; 6,944 KB
testcase_23	AC	223 ms; 6,940 KB
testcase_24	AC	51 ms; 6,944 KB
testcase_25	AC	49 ms; 6,940 KB
testcase_26	AC	1 ms; 6,944 KB
testcase_27	AC	2 ms; 6,940 KB
testcase_28	AC	2 ms; 6,940 KB
testcase_29	AC	2 ms; 6,940 KB

ソースコード

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll solve() {
    ll N, K, P;
    cin >> N >> K >> P;
    vector<ll> A(N), B(N);
    for ( int i = 0; i < N; i++ ) cin >> A[i];
    for ( int i = 0; i < N; i++ ) cin >> B[i];
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());

    auto get_le = [&](ll x) -> ll {
        ll s = 0;
        for ( int i = 0; i < N; i++ ) {
            s += upper_bound(B.begin(), B.end(), x-A[i]) - lower_bound(B.begin(), B.end(), -A[i]);
            s += upper_bound(B.begin(), B.end(), P+x-A[i]) - lower_bound(B.begin(), B.end(), P-A[i]);
        }
        return s;
    };
    
    // 単調非減少関数f(x), x:定義域[l,r), 戻り値は [l,r]
    // y <= f(x) となる最小のx
    auto lower_bound_f = [](ll l, ll r, ll y, auto f) -> ll {
        l--;
        while ( r-l > 1 ) {
            ll m = l + (r-l)/2;
            ll fx = f(m);
            if ( y <= fx ) r = m;
            else l = m;
        }
        return r;
    };

    ll ans = lower_bound_f(0,P,K,get_le);
    return ans;
}

int main() {
    auto ans = solve();
    cout << ans << "\n";
    return 0;
}