Submission #544498

#	Time	Username	Problem	Language	Result	Execution time	Memory
544498		model_code	Sightseeing in Kyoto (JOI22_kyoto)	C++17	100 / 100	414 ms	17504 KiB

kyoto

#include <array>
#include <climits>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
using ll = long long;
const ll INF = LLONG_MAX / 4;
void chmin(ll& a, ll b){ if(a > b) a = b; }

template<class T, class F> struct erasable_heap{
    priority_queue<T, vector<T>, F> q, e;
    erasable_heap(F f, vector<T> v): q(f, v), e(f, v){}
    void push(T a){ q.push(a); }
    void erase(T a){
        e.push(a);
        while(q.size() && q.top() == e.top()){
            q.pop();
            e.pop();
        }
    }
    void pop(){ erase(top()); }
    T top() const { return q.top(); }
    size_t size() const { return q.size() - e.size(); }
};
int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    ll H, W;
    cin >> H >> W;
    vector<ll> A(H), B(W);
    for(ll& a : A) cin >> a;
    for(ll& b : B) cin >> b;
    vector<ll> nextA(H - 1), nextB(W - 1);
    for(ll i = 0; i < H - 1; i++) nextA[i] = i + 1;
    for(ll i = 0; i < W - 1; i++) nextB[i] = i + 1;
    auto comp = [&](const auto& a, const auto& b){
        if(a[0] * b[1] != a[1] * b[0]) return a[0] * b[1] < a[1] * b[0];
        if(a[1] != b[1]) return a[1] < b[1];
        return a[2] < b[2];
    };
    erasable_heap qA(comp, vector<array<ll, 3>>{}), qB = qA;
    // {差分の分子, 差分の分母, 始点の idx}
    for(ll i = 0; i < H - 1; i++) qA.push({A[i + 1] - A[i], 1, i});
    for(ll i = 0; i < W - 1; i++) qB.push({B[i + 1] - B[i], 1, i});
    qA.push({(ll)-1.1e12, 1, -1});
    qB.push({(ll)-1.1e12, 1, -1});
    ll ans = 0;
    while(qA.size() > 1 || qB.size() > 1){
        if(comp(qB.top(), qA.top())){
            auto [p, q, i] = qA.top();
            qA.pop();
            const int j = nextA[i];
            if(j == A.size() - 1){
                while(q--){
                    ans += B.back();
                    A.pop_back();
                }
            }
            else{
                const int k = nextA[j];
                qA.erase({A[k] - A[j], k - j, j});
                nextA[i] = k;
                qA.push({A[k] - A[i], k - i, i});
            }
        }
        else{
            auto [p, q, i] = qB.top();
            qB.pop();
            const int j = nextB[i];
            if(j == B.size() - 1){
                while(q--){
                    ans += A.back();
                    B.pop_back();
                }
            }
            else{
                const int k = nextB[j];
                qB.erase({B[k] - B[j], k - j, j});
                nextB[i] = k;
                qB.push({B[k] - B[i], k - i, i});
            }
        }
    }
    cout << ans << endl;
}

Compilation message (stderr)

kyoto.cpp: In function 'int main()':
kyoto.cpp:54:18: warning: comparison of integer expressions of different signedness: 'const int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |             if(j == A.size() - 1){
      |                ~~^~~~~~~~~~~~~~~
kyoto.cpp:71:18: warning: comparison of integer expressions of different signedness: 'const int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |             if(j == B.size() - 1){
      |                ~~^~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 60 / 60