Submission #1324053

#	Time	Username	Problem	Language	Result	Execution time	Memory
1324053		sh_qaxxorov_571	Just Long Neckties (JOI20_ho_t1)	C++20	100 / 100	70 ms	7108 KiB

ho_t1

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * JOI 2020 Final - Neckties
 * Vaqt murakkabligi: O(N log N) - tartiblash tufayli
 * Xotira murakkabligi: O(N)
 */

struct Tie {
    int val, id;
};

bool compareTies(const Tie& a, const Tie& b) {
    return a.val < b.val;
}

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

    int N;
    cin >> N;

    vector<Tie> A(N + 1);
    for (int i = 0; i < N + 1; i++) {
        cin >> A[i].val;
        A[i].id = i;
    }

    vector<int> B(N);
    for (int i = 0; i < N; i++) {
        cin >> B[i];
    }

    // Tartiblaymiz
    sort(A.begin(), A.end(), compareTies);
    sort(B.begin(), B.end());

    // pref[i] -> A[0...i-1] va B[0...i-1] juftligidan maksimal g'alatilik
    vector<int> pref(N + 1, 0);
    for (int i = 0; i < N; i++) {
        pref[i + 1] = max(pref[i], max(0, A[i].val - B[i]));
    }

    // suff[i] -> A[i+1...N] va B[i...N-1] juftligidan maksimal g'alatilik
    vector<int> suff(N + 1, 0);
    for (int i = N - 1; i >= 0; i--) {
        suff[i] = max(suff[i + 1], max(0, A[i + 1].val - B[i]));
    }

    // Asl tartibdagi javoblarni saqlash uchun
    vector<int> results(N + 1);
    for (int i = 0; i <= N; i++) {
        // Agar A[i] (tartiblangan massivdagi i-chi element) olib tashlansa
        results[A[i].id] = max(pref[i], suff[i]);
    }

    for (int i = 0; i <= N; i++) {
        cout << results[i] << (i == N ? "" : " ");
    }
    cout << endl;

    return 0;
}

• Subtask 1: 1 / 1
• Subtask 2: 8 / 8
• Subtask 3: 91 / 91