Submission #1179905

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179905		bbartek	Just Long Neckties (JOI20_ho_t1)	C++20	100 / 100	62 ms	7352 KiB

ho_t1

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define st first
#define nd second
#define pb push_back

const int maxn = 2e5+7;

int wynik[maxn];
int pref[maxn];

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

    int n,a;
    cin>>n;

    vector<pair<int,int>> v1;
    vector<int> v2;

    for(int i=1;i<=n+1;i++){
        cin>>a;
        v1.pb({a,i});
    }
    sort(v1.begin(),v1.end());

    for(int i=1;i<=n;i++){
        cin>>a;
        v2.pb(a);
    }

    sort(v2.begin(),v2.end());

    pref[0] = max(0,v1[0].st - v2[0]);
    for(int i=1;i<n;i++){
        pref[i] = max(pref[i-1],max(0,v1[i].st-v2[i]));
    }

    wynik[v1[n].nd] = pref[n-1];

    int suf = 0,akt;

    for(int i=n-1;i>=0;i--){
        akt = max(0,v1[i+1].st - v2[i]);
        suf = max(suf,akt);
        if(i != 0){
            wynik[v1[i].nd] = max(suf,pref[i-1]);
        }
        else{
            wynik[v1[i].nd] = suf;
        }
    }

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

    return 0;
}

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