Submission #941681

#	Time	Username	Problem	Language	Result	Execution time	Memory
941681		alextodoran	Ants and Sugar (JOI22_sugar)	C++17	0 / 100	1525 ms	2512 KiB

sugar

/**
 _  _   __  _ _ _  _  _ _
 |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) {
        int i = S.begin()->second;
        S.erase(S.begin());
        if (i > 0) {
            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((ld) (A[i] - A[l]) / (i - l), l));
                S.insert(make_pair((ld) (A[r] - A[l]) / (r - l), l));
            }
        } else {
            i = -i;
            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((ld) (B[i] - B[l]) / (i - l), -l));
                S.insert(make_pair((ld) (B[r] - B[l]) / (r - l), -l));
            }
        }
    }
    cout << answer << "\n";

    return 0;
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 16
• Subtask 3: 0 / 26
• Subtask 4: 0 / 52