Submission #979845

#	Time	Username	Problem	Language	Result	Execution time	Memory
979845		IUA_Hasin	Just Long Neckties (JOI20_ho_t1)	C++17	100 / 100	175 ms	25500 KiB

ho_t1

#include <bits/stdc++.h>

#define ll                                  long long
#define ld                                  long double
#define endl                                "\n"

using namespace std;


int main(){
    #if __has_include("LOCAL.hh")
        #include "LOCAL.hh"
    #endif

    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
        using namespace std::chrono;
        cout << fixed << setprecision(9);
        auto begin = steady_clock::now();
    #else
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);
    #endif



    ll n;
    cin>>n;
    vector<pair<ll, ll>> v;
    ll brr[n];

    for(int i=0; i<n+1; i++){
        ll x;
        cin>>x;
        v.push_back({x, i});
    }

    for(int i=0; i<n; i++){
        cin>>brr[i];
    }
    sort(v.begin(), v.end());
    sort(brr, brr+n);

    ll diff1[n];
    ll diff2[n];
    for(int i=0; i<n; i++){
        ll b = brr[i];
        ll a1 = v[i].first;
        ll a2 = v[i+1].first;
        ll temp1 = max((ll)0, a1-b);
        ll temp2 = max((ll)0, a2-b);
        diff1[i] = temp1;
        diff2[i] = temp2;
    }

    multiset<ll> s;
    for(int i=0; i<n; i++){
        s.insert(diff1[i]);
    }

    ll ans[n+1];
    ll r = n;
    while(r>=0){
        // for(auto u : s){
        //     cout << u << " ";
        // }
        // cout<<endl;
        //cout<<endl;
        ll tempind = v[r].second;
        auto it = s.end();
        it--;
        ll temp = *it;
        ans[tempind] = temp;
        //cout << temp << " " << tempind << endl;
        //cout<<endl;
        //s.erase(it);
        ll next = diff2[r-1];
        ll now = diff1[r-1];
        auto dlt = s.find(now);
        if(dlt==s.end()){
            dlt--;
        }
        s.erase(dlt);
        s.insert(next);

        r--;
    }

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






    #ifdef LOCAL
        auto end = steady_clock::now();
        cout << "\nTime : " 
             << (ld)duration_cast<nanoseconds>
                (end - begin).count()/1000000000 
             << "s" << endl;
    #endif


    return 0;
}

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