Submission #420040

#	Time	Username	Problem	Language	Result	Execution time	Memory
420040		Marceantasy	Just Long Neckties (JOI20_ho_t1)	C++17	100 / 100	131 ms	10820 KiB

ho_t1

#include <bits/stdc++.h>

using namespace std; 

#define ll long long
#define ar array

const int mxN = 2e5+10; 
int n, b[mxN];
ar<int, 2> a[mxN]; 
int dif1[mxN], dif2[mxN], ans[mxN]; 

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

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

    for(int i = 0; i<n; ++i){   
        dif1[i] = max(a[i+1][0]-b[i], 0); 
        dif2[i+1] = max(a[i][0]-b[i], 0); 
    }
    for(int i = n-1; i>=0; --i){
        dif1[i] = max(dif1[i], dif1[i+1]); 
    }
    for(int i = 1; i<=n; ++i){
        dif2[i] = max(dif2[i], dif2[i-1]); 
    }
    for(int i = 0; i<=n; ++i){
        ans[a[i][1]] = max(dif1[i], dif2[i]); 
    }
    for(int i = 0; i<=n; ++i){
        cout << ans[i] << " "; 
    }

}

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