Submission #1331791

#TimeUsernameProblemLanguageResultExecution timeMemory
1331791lywoemGrid Coloring (JOI25_ho_t1)C++20
100 / 100
263 ms50540 KiB
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define l(a, b, i) for (ll i = a; i < b; i++)
#define rl(a, b, i) for (ll i = a; i >= b; i--)
#define vpair vector<pair<ll, ll>>
#define inf LLONG_MAX
#define ninf LLONG_MIN

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ll N; cin >> N; vector<ll> vecA(N + 1, 0), vecB(N + 1, 0);
    map<ll, ll> mp;
    l(1, N + 1, i) {cin >> vecA[i]; mp[vecA[i]]++;}
    l(1, N + 1, i) {cin >> vecB[i]; mp[vecB[i]]++;}
    mp[vecA[1]]--;

    vector<ll> preA(N, 0); // prefix max nhé
    preA[1] = vecA[2];
    l(2, N, i) preA[i] = max(preA[i - 1], vecA[i + 1]);

    vector<ll> preB(N, 0); 
    preB[1] = vecB[2];
    l(2, N, i) preB[i] = max(preB[i - 1], vecB[i + 1]);

    set<ll> st;
    l(1, N, i) st.insert(preA[i]);
    l(1, N, i) st.insert(preB[i]);

    ll prev = 0;
    for (ll x : st) {
        auto ubA = upper_bound(preA.begin() + 1, preA.end(), x);
        ll wA = ubA - (preA.begin() + 1);

        auto ubB = upper_bound(preB.begin() + 1, preB.end(), x);
        ll wB = ubB - (preB.begin() + 1);

        ll area = wA * wB;
        mp[x] += area - prev;
        prev = area;
    }

    ll ans = 0;
    ll num = 0;
    for (auto i = mp.begin(); i != mp.end(); i++) {
        if (i -> second > ans) {
            ans = i -> second;
            num = i -> first;
        }

        else if (i -> second == ans) {
            if (i -> first > num) num = i -> first;
        }
    }

    cout << num << ' ' << ans;
}
#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...