Submission #1158324

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158324		dnnnda	Just Long Neckties (JOI20_ho_t1)	C++20	100 / 100	202 ms	15712 KiB

ho_t1

#include<bits/stdc++.h>
using namespace std;
#define S second
#define F first
#define ll long long
//#define int long long
//#pragma GCC optimize("Ofast, unroll-loop")
//#pragma GCC target("avx,avx2")
#pragma GCC optimize("O3")
const int inf=0x3f3f3f3f;
const ll inff=0x3f3f3f3f3f3f3f3f;
//const int X=1000000007;
const int X=998244353;

int a[200005], b[200005], ans[200005];
vector<pair<int,int>> p;
multiset<int> s;

signed main(){
    ios::sync_with_stdio(0), cin.tie(0);
    int n; cin >> n;
    for(int i=0 ; i<n+1 ; i++) cin >> a[i];
    for(int i=0 ; i<n ; i++) cin >> b[i];
    for(int i=0 ; i<n+1 ; i++) p.push_back({a[i],i});
    sort(p.begin(),p.end());
    sort(a,a+n+1);
    sort(b,b+n);
    for(int i=0 ; i<n ; i++) s.insert(a[i+1]-b[i]);
    ans[p[0].S]=*s.rbegin();
    for(int i=1 ; i<=n ; i++){
        s.erase(s.find(a[i]-b[i-1]));
        s.insert(a[i-1]-b[i-1]);
        ans[p[i].S]=*s.rbegin();
    }
    for(int i=0 ; i<=n ; i++) cout << max(0,ans[i]) << (i==n ? '\n' : ' ');



    return 0;
}

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