Submission #1280345

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280345		hanguyendanghuy	Just Long Neckties (JOI20_ho_t1)	C++20	9 / 100	56 ms	6636 KiB

ho_t1

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define fi first
#define se second
constexpr ll MAXN=1e5+5,MAXV=3e5,MOD=1e9+7,INF=1e18;
ll n,m,i,j,p,k,ans[MAXN],dem,st,en,b[MAXN];
struct h{
    ll a,id;
} a[MAXN];
bool cmp(h x,h y){
    return x.a<y.a;
}
struct seg{
    ll c[4*MAXN];
    void build(ll id,ll l,ll r){
        if(l==r) c[id]=a[l].a-b[l];
        else{
            ll m=(l+r)/2;
            build(id*2,l,m);
            build(id*2+1,m+1,r);
            c[id]=max(c[id*2],c[id*2+1]);
        }
    }
    void update(ll id,ll l,ll r,ll pos,ll val){
        if(l>pos||r<pos) return;
        else if(l==r)
            c[id]=val;
        else{
            ll m=(l+r)/2;
            update(id*2,l,m,pos,val);
            update(id*2+1,m+1,r,pos,val);
            c[id]=max(c[id*2],c[id*2+1]);
        }
    }
    ll get(){
        return c[1];
    }
} seg;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(i=0;i<=n;i++) cin>>a[i].a,a[i].id=i;
    for(i=1;i<=n;i++) cin>>b[i];
    sort(a,a+n+1,cmp);
    sort(b+1,b+n+1);
    seg.build(1,1,n);
    ans[a[0].id]=seg.get();
    for(i=1;i<=n;i++){
        seg.update(1,1,n,i,a[i-1].a-b[i]);
        ans[a[i].id]=seg.get();
    }
    for(i=0;i<=n;i++)
        cout<<ans[i]<<" ";
}

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