제출 #958801

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
958801		LucaIlie	Sightseeing in Kyoto (JOI22_kyoto)	C++17	0 / 100	2 ms	2396 KiB

kyoto

#include <bits/stdc++.h>

using namespace std;

struct rc {
    int type, ind, prv;
    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], b[MAX_M], prvA[MAX_N], nxtA[MAX_N], prvB[MAX_M], nxtB[MAX_M];
priority_queue<rc> pq;

int main() {
    int n, m;

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

    prvA[0] = -1;
    for ( int i = 1; 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] = -1;

    prvB[0] = -1;
    for ( int i = 1; i < m; i++ ) {
        pq.push( { 1, i, i - 1, (double)b[i] - b[i - 1] } );
        prvB[i] = i - 1;
        nxtB[i - 1] = i;
    }
    nxtB[n - 1] = -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;

        //printf( "%d %d: %d %d %d ", n, m, x.type, x.ind, x.prv );
        //cout << x.value << "\n";

        if ( x.type == 0 ) {
            if ( nxtA[x.ind] == -1 ) {
                ans += (long long)b[m - 1] * (x.ind - prvA[x.ind]);
                n = prvA[x.ind] + 1;
            } else {
                pq.push( { 0, nxtA[x.ind], prvA[x.ind], (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 - 1] * (x.ind - prvB[x.ind]);
                m = prvB[x.ind] + 1;
            } else {
                pq.push( { 1, nxtB[x.ind], prvB[x.ind], (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";
    }

    cout << ans << "\n";

    return 0;
}

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