Submission #566953

#	Time	Username	Problem	Language	Result	Execution time	Memory
566953		katwamiaw	Just Long Neckties (JOI20_ho_t1)	C++14	100 / 100	249 ms	8592 KiB

ho_t1

#include<bits/stdc++.h>
#define ll long long
#define no cout << "NO\n"
#define yes cout << "YES\n"
#define endl '\n'
#define pb push_back
using namespace std ;
//fflush(stdout) ;

const int Max_n=2e5+10 ;
int a[Max_n] , b[Max_n] , f[Max_n] , c[Max_n] ;
int pref[Max_n] , suff[Max_n] ;
vector<array<int,2>>v ;

int main(){
    int n ; cin >> n ;
    for(int i=0 ; i<n+1 ; i++){
        cin >> a[i] ;
        v.push_back({a[i],i}) ;
    }
    for(int i=0 ; i<n ; i++) cin >> b[i] ;

    sort(a,a+n+1) ;
    sort(v.begin(),v.end()) ;
    sort(b,b+n) ;

    for(int i=0 ; i<n+1 ; i++){
        f[i]=v[i][1] ;
    }

    pref[0]=0 ;
    for(int i=0 ; i<n ; i++){
        int k=max((a[i]-b[i]),0) ;
        pref[i+1]=max(pref[i],k) ;
    }
    suff[n+1]=0 ;
    for(int i=n ; i>=1 ; i--){
        int k=max((a[i]-b[i-1]),0) ;
        suff[i]=max(suff[i+1],k) ;
    }

    for(int i=1 ; i<=n+1 ; i++){
        int ans=max(pref[i-1],suff[i]) ;
        c[f[i-1]]=ans ;
    }

    for(int i=0 ; i<n+1 ; i++) cout << c[i] << ' ' ;
}

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