제출 #554960

#제출 시각아이디문제언어결과실행 시간메모리
554960PietraJust Long Neckties (JOI20_ho_t1)C++14
100 / 100
248 ms20768 KiB
#include<bits/stdc++.h>
#define int long long 
using namespace std ; 

// n caras - bj é o inicial, ai o q ele pode escolher 
// oddity - max(a-b, 0) - max min p cada k (oq o ceo pega)
// pega i i -> liga - bi + ai+1 (mlr doq dxr p outro)

const int maxn = 2e5 + 5 ; 

multiset<int> ligs ;

int n, c[maxn], b[maxn] ; 
pair<int,int> a[maxn] ; 

int32_t main(){

	ios_base::sync_with_stdio(false) ; cin.tie(NULL) ; 

	cin >> n ; 

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

	for(int i = 1 ; i <= n ; i++) cin >> b[i] ;

	sort(b + 1, b + 1 + n) ; sort(a + 1, a + 2 + n) ; 
    
    //começo 
    
    for(int i = 1 ; i <= n ; i++) ligs.insert(max(0LL, a[i].first - b[i])) ; 

    auto it = ligs.end() ; it-- ;
    c[a[n+1].second] = (*it) ; 

    for(int i = n ; i > 0 ; i--){ 
    	ligs.erase(ligs.find(max(0LL, a[i].first - b[i]))) ; 
    	ligs.insert(max(0LL, a[i+1].first - b[i])) ; 
    	auto it = ligs.end() ; it-- ; 
    	c[a[i].second] = (*it) ; 
    }

    for(int i = 1 ; i <= n + 1 ; i++) cout << c[i] << " " ; 
    cout << "\n" ; 

}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...