제출 #1330227

#제출 시각아이디문제언어결과실행 시간메모리
1330227bradley0927Grid Coloring (JOI25_ho_t1)C++20
25 / 100
403 ms47392 KiB
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <set>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> A(n + 1), B(n + 1);
    for (int i = 1; i <= n; i++) cin >> A[i];
    for (int j = 1; j <= n; j++) cin >> B[j];

    // prefix maxes
    vector<int> PA(n + 1), PB(n + 1);
    PA[1] = A[1];
    for (int i = 2; i <= n; i++) PA[i] = max(PA[i - 1], A[i]);
    PB[1] = B[1];
    for (int j = 2; j <= n; j++) PB[j] = max(PB[j - 1], B[j]);

    // count frequency in PA and PB
    map<int, long long> cntA, cntB;
    for (int i = 1; i <= n; i++) cntA[PA[i]]++;
    for (int j = 1; j <= n; j++) cntB[PB[j]]++;

    // collect all colors
    set<int> colors;
    for (auto &[v,_]: cntA) colors.insert(v);
    for (auto &[v,_]: cntB) colors.insert(v);

    long long bestCount = 0;
    int bestColor = 0;
    long long cumA = 0, cumB = 0; // cumulative counts ≤ c

    for (int c: colors) {
        long long R = cntA.count(c) ? cntA[c] : 0;
        long long C = cntB.count(c) ? cntB[c] : 0;
        cumA += R;
        cumB += C;
        // R' = cumA, C' = cumB, R_less = cumA - R, C_less = cumB - C
        long long count = R * cumB + (cumA - R) * C;
        if (count > bestCount || (count == bestCount && c > bestColor)) {
            bestCount = count;
            bestColor = c;
        }
    }
    cout << bestColor << " " << bestCount << "\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...