Submission #566970

#	Time	Username	Problem	Language	Result	Execution time	Memory
566970		Abdulmohsen1284	Just Long Neckties (JOI20_ho_t1)	C++14	100 / 100	98 ms	13200 KiB

ho_t1

#include"bits/stdc++.h"
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class x>
using ordered_set = tree<x, null_type,less<x>, rb_tree_tag,tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

long long b[2000005],pre[2000005],suf[2000005],ans[2000005],plc[2000005];
pair <long long, long long> a[2000005];
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    long long n;
    cin>>n;
    vector < pair <long long, long long > > c;
    for(int i=1;i<=n+1;i++){
        cin>>a[i].first;
        a[i].second=i;
    }
    for(int i=1;i<=n;i++)
        cin>>b[i];
    sort(b+1,b+n+1);
    sort(a+1,a+n+2);
    for(int i=1;i<=n+1;i++)
    {
        plc[a[i].second]=i;
    }
    for(int i=1;i<=n;i++)
    {
        pre[i]=max(pre[i-1],a[i].first-b[i]);
        //cout<<pre[i]<<" ";
    }
    //cout<<"\n";
    for(int i=n;i>=1;i--)
    {
        suf[i]=max(suf[i+1],a[i+1].first-b[i]);
        //cout<<suf[i]<<" ";
    }
    //cout<<"\n";
    for(int i=1;i<=n+1;i++)
    {
        ans[a[i].second]=max(pre[plc[a[i].second]-1],suf[plc[a[i].second]]);
        //cout<<pre[a[i].first-1]<<" "<<suf[a[i].first]<<" "<<a[i].first<<"f\n";
    }
    for(int i=1;i<=n+1;i++)
        cout<<ans[i]<<" ";
}

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