Submission #845903

#	Time	Username	Problem	Language	Result	Execution time	Memory
845903		AlphaMale06	Just Long Neckties (JOI20_ho_t1)	C++17	100 / 100	110 ms	11348 KiB

ho_t1

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5+3;
int st[4*N];
struct wind{
    int ind;
    int val;
};
wind a[N];
int b[N];
bool cmp(wind A, wind B){
    return A.val<B.val;
}
void Build(int node, int l, int r){
    if(l>r)return;
    if(l==r){
        st[node]=max(0, a[l+1].val-b[l]);
        return;
    }
    int mid=(l+r)/2;
    Build(2*node+1, l, mid);
    Build(2*node+2, mid+1, r);
    st[node]=max(st[2*node+1], st[2*node+2]);
}

void Update(int node, int l, int r, int ind){
    if(l>r || l>ind || r<ind)return;
    if(l==r){
        st[node]=max(a[l].val-b[l], 0);
        return;
    }
    int mid=(l+r)/2;
    Update(2*node+1, l, mid, ind);
    Update(2*node+2, mid+1, r, ind);
    st[node]=max(st[2*node+1], st[2*node+2]);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    for(int i=0; i< n+1; i++){
        cin >> a[i].val;
        a[i].ind=i;
    }
    for(int i=0; i< n; i++){
        cin >> b[i];
    }
    sort(a, a+n+1, cmp);
    sort(b, b+n);
    Build(0, 0, n-1);
    int ans[n+1];
    ans[a[0].ind]=st[0];
    for(int i=1; i<=n; i++){
        Update(0, 0, n-1, i-1);
        ans[a[i].ind]=st[0];
    }
    for(int i=0; i<=n; i++){
        cout << ans[i] << " ";
    }
}

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