Submission #504084

#	Time	Username	Problem	Language	Result	Execution time	Memory
504084		lucri	Just Long Neckties (JOI20_ho_t1)	C++17	100 / 100	233 ms	10720 KiB

ho_t1

#include <iostream>
#include <algorithm>
using namespace std;
int n,b[200010],r[200010];
struct cravata{int val,poz;}a[200010],dif[200010];
bool comp1(cravata a,cravata b)
{
    return a.val<b.val;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n+1;++i)
    {
        cin>>a[i].val;
        a[i].poz=i;
    }
    for(int i=1;i<=n;++i)
        cin>>b[i];
    sort(a+1,a+n+2,comp1);
    sort(b+1,b+n+1);
    for(int i=1;i<=n;++i)
    {
        dif[i].poz=i;
        dif[i].val=max(0,a[i].val-b[i]);
    }
    sort(dif+1,dif+n+1,comp1);
    r[a[n+1].poz]=dif[n].val;
    int maxa=0,poza=n;
    for(int i=n;i>=1;--i)
    {
        maxa=max(maxa,a[i+1].val-b[i]);
        while(dif[poza].val>maxa&&dif[poza].poz>=i)
            --poza;
        r[a[i].poz]=max(maxa,dif[poza].val);
    }
    for(int i=1;i<=n+1;++i)
        cout<<r[i]<<' ';
    return 0;
}

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