Submission #1115591

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115591		staszic_ojuz	Just Long Neckties (JOI20_ho_t1)	C++17	100 / 100	98 ms	24824 KiB

ho_t1

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

using namespace std;

typedef long long ll;

struct dat {
    ll a;
    ll i;
    dat(): a(0), i(0) {};
};
bool operator<(dat a, dat b) {
    return a.a < b.a;
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    ll n; cin >> n;
    vector<dat> wol(n + 1);
    for(int i = 0; i < n + 1; i++) {
        cin >> wol[i].a;
        wol[i].i = i;
    }
    vector<ll> ma(n);
    for(int i = 0; i < n; i++) {
        cin >> ma[i];
    }
    
    sort(wol.begin(), wol.end());
    sort(ma.begin(), ma.end());

    // cout << "WOL\n";
    // for(int i = 0; i < n + 1; i++) {
    //     cout << wol[i].a << " " << wol[i].i << '\n';
    // }

    // vector<ll> pout(n + 1, 0);
    // for(int i = 0; i < n + 1; i++) {
    //     pout[wol[i].i] = i;
    // }

    vector<dat> par1(n);
    vector<dat> par2(n);
    for(int i = 0; i < n; i++) {
        par1[i].i = wol[i].i;
        par1[i].a = max(wol[i].a - ma[i], (ll)0);
        par2[i].i = wol[i + 1].i;
        par2[i].a = max(wol[i + 1].a - ma[i], (ll)0);
    }
    vector<dat> pref(n + 2);
    vector<dat> suff(n + 2);
    pref[0].a = 0;
    pref[n + 1].a = 0;
    
    suff[0].a = 0;
    suff[n + 1].a = 0;    
    pref[0].i = par2[n - 1].i;
    for(int i = 1; i < n + 1; i++) {
        if(pref[i - 1].a > par1[i - 1].a) {
            pref[i].a = pref[i - 1].a;
        } else {
            pref[i].a = par1[i - 1].a;    
        }

        pref[i].i = par1[i - 1].i;
    }
    suff[n].i = par1[0].i;
    for(int i = n -1;i>=0;i--) {
        if(suff[i + 1].a > par2[i].a) {
            suff[i].a = suff[i + 1].a;
        } else {
            suff[i].a = par2[i].a;    
        }
        suff[i].i = par2[i].i;
    }
    // cout << "PREF\n";
    // for(int i = 0; i < n + 1; i++) {
    //     cout << pref[i].a << " " << pref[i].i << '\n';
    // }
    // cout << "SUFF\n";
    // for(int i = 0; i < n + 1; i++) {
    //     cout << suff[i].a  << " " << suff[i].i << '\n';
    // }

    vector<ll> out(n + 1);

    for(int i = 0; i < n + 1; i++) {
        //cout   << "pout[i]: " << pout[i] <<", i: " << i << "pout: "<< pout[i] << endl;
        ll res = pref[i].a;
        res =max(pref[i].a, suff[i].a);
        out[wol[i].i] = res;
        //cout << wol[i].i << " ";
    }

    // cout << "pout\n";
    // for(int i = 0; i < n + 1; i++) {
    //     cout << out[i] << '\n';
    // }

    for(int i = 0; i < n + 1; i++) {
        cout << out[i] << " ";
    }

    return 0;
}

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