Submission #310068

#	Time	Username	Problem	Language	Result	Execution time	Memory
310068		vipghn2003	Just Long Neckties (JOI20_ho_t1)	C++14	100 / 100	211 ms	11384 KiB

ho_t1

#include<bits/stdc++.h>

using namespace std;

const int N=2e5+5;
int n,b[N],can[N],ST[4*N],res[N];
pair<int,int>a[N];

int get(int id,int l,int r,int L,int R)
{
    if (r<L||R<l) return 0;
    if (L<=l&&r<=R) return ST[id];
    int mid=(l+r)/2;
    return max(get (id*2,l,mid,L,R),get(id*2+1,mid+1,r,L,R));
}

void update(int id,int l,int r,int u,int x)
{
    if(r==l&&l==u)
    {
        ST[id]=x;
        return;
    }
    if(u>r||u<l) return;
    int mid=(l+r)/2;
    update(id*2,l,mid,u,x);
    update(id*2+1,mid+1,r,u,x);
    ST[id]=max(ST[id*2],ST[id*2+1]);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n;
    for(int i=1;i<=n+1;i++)
    {
        cin>>a[i].first;
        a[i].second=i;
    }
    sort(a+1,a+n+2);
    for(int i=1;i<=n;i++) cin>>b[i];
    sort(b+1,b+n+1);
    for(int i=2;i<=n+1;i++) update(1,1,n,i-1,a[i].first-b[i-1]);
    for(int i=1;i<=n+1;i++)
    {
        res[a[i].second]=get(1,1,n,1,n);
        update(1,1,n,i,a[i].first-b[i]);
    }
    for(int i=1;i<=n+1;i++) cout<<res[i]<<' ';
}

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