Submission #958802

#	Time	Username	Problem	Language	Result	Execution time	Memory
958802		LucaIlie	Sightseeing in Kyoto (JOI22_kyoto)	C++17	100 / 100	175 ms	14780 KiB

kyoto

#include <bits/stdc++.h>

using namespace std;

struct rc {
    int type, ind, prv;
    long double value;

    bool operator < ( const rc &x ) const {
        return value < x.value;
    }
};

const int MAX_N = 1e5;
const int MAX_M = 1e5;
int a[MAX_N + 1], b[MAX_M + 1], prvA[MAX_N + 1], nxtA[MAX_N + 1], prvB[MAX_M + 1], nxtB[MAX_M + 1];
priority_queue<rc> pq;

int main() {
    int n, m;

    cin >> n >> m;
    for ( int i = 1; i <= n; i++ )
        cin >> a[i];
    for ( int i = 1; i <= m; i++ )
        cin >> b[i];

    prvA[1] = 0;
    for ( int i = 2; i <= n; i++ ) {
        pq.push( { 0, i, i - 1, (double)a[i] - a[i - 1] } );
        prvA[i] = i - 1;
        nxtA[i - 1] = i;
    }
    nxtA[n] = -1;

    prvB[1] = -1;
    for ( int i = 2; i <= m; i++ ) {
        pq.push( { 1, i, i - 1, (long double)b[i] - b[i - 1] } );
        prvB[i] = i - 1;
        nxtB[i - 1] = i;
    }
    nxtB[m] = -1;

    long long ans = 0;
    while ( !pq.empty() ) {
        auto x = pq.top();
        pq.pop();

        if ( (x.type == 0 && prvA[x.ind] != x.prv) || (x.type == 1 && prvB[x.ind] != x.prv) )
            continue;

        if ( x.type == 0 ) {
            if ( nxtA[x.ind] == -1 ) {
                ans += (long long)b[m] * (x.ind - prvA[x.ind]);
                n = prvA[x.ind];
            } else {
                pq.push( { 0, nxtA[x.ind], prvA[x.ind], (long double)(a[nxtA[x.ind]] - a[prvA[x.ind]]) / (nxtA[x.ind] - prvA[x.ind]) } );
                prvA[nxtA[x.ind]] = prvA[x.ind];
            }
            nxtA[prvA[x.ind]] = nxtA[x.ind];
        } else {
            if ( nxtB[x.ind] == -1 ) {
                ans += (long long)a[n] * (x.ind - prvB[x.ind]);
                m = prvB[x.ind];
            } else {
                pq.push( { 1, nxtB[x.ind], prvB[x.ind], (long double)(b[nxtB[x.ind]] - b[prvB[x.ind]]) / (nxtB[x.ind] - prvB[x.ind]) } );
                prvB[nxtB[x.ind]] = prvB[x.ind];
            }
            nxtB[prvB[x.ind]] = nxtB[x.ind];
        }
    }

    cout << ans << "\n";

    return 0;
}

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