Submission #941679

#	Time	Username	Problem	Language	Result	Execution time	Memory
941679		alextodoran	Sightseeing in Kyoto (JOI22_kyoto)	C++17	0 / 100	1 ms	2396 KiB

kyoto

/**
 _  _   __  _ _ _  _  _ _
 |a  ||t  ||o    d | |o  |
| __    _| | _ | __|  _ |
| __ |/_  | __  /__\ / _\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int N_MAX = 100000;
const int M_MAX = 100000;

int N, M;
int A[N_MAX + 2];
int B[M_MAX + 2];

int nxt_A[N_MAX + 2];
int prv_A[N_MAX + 2];
int nxt_B[M_MAX + 2];
int prv_B[M_MAX + 2];

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        cin >> A[i];
    }
    for (int i = 1; i <= M; i++) {
        cin >> B[i];
    }
    for (int i = 0; i + 1 <= N; i++) {
        nxt_A[i] = i + 1;
        prv_A[i + 1] = i;
        nxt_B[i] = i + 1;
        prv_B[i + 1] = i;
    }
    set <pair <ld, int>> S;
    for (int i = 1; i + 1 <= N; i++) {
        S.insert(make_pair(A[i + 1] - A[i], i));
        S.insert(make_pair(B[i + 1] - B[i], -i));
    }
    ll answer = 0;
    while (S.empty() == false) {
        pair <int, int> p = *S.begin();
        S.erase(S.begin());
        if (p.second > 0) {
            int i = p.second;
            int l = prv_A[i], r = nxt_A[i];
            nxt_A[l] = r;
            prv_A[r] = l;
            if (l == 0) {
                answer += (ll) B[nxt_B[0]] * (r - i);
            }
            if (l != 0) {
                S.erase(make_pair((A[i] - A[l]) / (i - l), l));
                S.insert(make_pair((A[r] - A[l]) / (r - l), l));
            }
        } else {
            int i = -p.second;
            int l = prv_B[i], r = nxt_B[i];
            nxt_B[l] = r;
            prv_B[r] = l;
            if (l == 0) {
                answer += (ll) A[nxt_A[0]] * (r - i);
            }
            if (l != 0) {
                S.erase(make_pair((B[i] - B[l]) / (i - l), -l));
                S.insert(make_pair((B[r] - B[l]) / (r - l), -l));
            }
        }
    }
    cout << answer << "\n";

    return 0;
}

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