Submission #554960

#	Time	Username	Problem	Language	Result	Execution time	Memory
554960		Pietra	Just Long Neckties (JOI20_ho_t1)	C++14	100 / 100	248 ms	20768 KiB

ho_t1

#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" ; 

}

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