Submission #906412

#	Time	Username	Problem	Language	Result	Execution time	Memory
906412		vjudge1	Just Long Neckties (JOI20_ho_t1)	C++17	100 / 100	75 ms	17236 KiB

ho_t1

#include<bits/stdc++.h>
#define ll long long
#define f first
#define s second
using namespace std;

ll n, b[(int)2e5+5], c1[(int)2e5+5], c2[(int)2e5+5], ans[(int)2e5+5];

pair <ll, ll> c[(int)2e5+5], a[(int)2e5+5];

int main(){
	
	ios_base::sync_with_stdio(0);
	
	cin.tie(0);
	
	cin>>n;
	
	for(int i = 1; i <= n+1; i++){
		
		cin>>a[i].f;
		
		a[i].s = i;
	}
	
	for(int i = 1; i <= n; i++) cin>>b[i];
	
	sort(a+1, a+n+2); sort(b+1, b+n+1);
	
	c1[0] = -1e18; c2[n+1] = -1e18;
	
	for(int i = 1; i <= n; i++){
		
		c[i].f = max(0ll, a[i].f-b[i]);
		
		c[i].s = max(0ll, a[i+1].f-b[i]);
		
		c1[i] = max(c1[i-1], c[i].f);
	}
	
	for(int i = n; i >= 1; i--){
		
		c2[i] = max(c2[i+1], c[i].s);
	}
	
	for(int i = 1; i <= n+1; i++){
		
		ans[a[i].s] = max(c1[i-1], c2[i]);
	}
	for(int i = 1; i <= n+1; i++){
		
		cout<<ans[i]<<" ";
	}
}

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