Submission #566962

#	Time	Username	Problem	Language	Result	Execution time	Memory
566962		birthdaycake	Just Long Neckties (JOI20_ho_t1)	C++17	100 / 100	205 ms	14852 KiB

ho_t1

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
#define mod 1000000007
#define boost ios_base::sync_with_stdio(false), cin.tie(NULL);
using namespace std;
 
 
 
int N,Left,Right,Type;

pair<int,int>a[4000001];
int b[4000001],ans[2000001];
int seg[4000001],seg2[4000001];



void Update(){
    int ind = N + Left - 1;
    seg[ind] = a[Left].first - b[Left - 1];
    while(ind /= 2) seg[ind] = max(seg[ind * 2], seg[ind * 2 + 1]);
    ind = N + Left - 1;
    seg2[ind] = a[Left - 1].first - b[Left - 1];
    while(ind /= 2) seg2[ind] = max(seg2[ind * 2], seg2[ind * 2 + 1]);
}


int Query(int l = 1, int r = N, int ind = 1){
    if(l > Right || r < Left) return 0;
    if(l >= Left && r <= Right){
        if(Type) return seg[ind];
        return seg2[ind];
    }
    int mid = (l + r) / 2;
    return max(Query(l, mid, ind * 2), Query(mid + 1, r, ind * 2 + 1));
}
signed main(){
    boost;
    
    
    
    
    int n; cin >> n;
    N = exp2(ceil(log2(n)));
    for(int i = 0; i < n + 1; i++){
        cin >> a[i].first;
        a[i].second = i;
    }
    sort(a,a+n+1);
    for(int i = 0; i < n; i++) cin >> b[i];
    sort(b,b+n);
    for(int i = 0; i < n; i++){
        Left = i + 1;
        Update();
    }
    for(int i = 0; i < n + 1; i++){
        int aa = 0;
        Left = 1; Right = i;
        if(Left <= Right){
            Type = 0;
            aa = max(aa,Query());
        }
        Left = i + 1; Right = n;
        if(Left <= Right){
            Type = 1;
            aa = max(aa,Query());
        }
        ans[a[i].second] = aa;
    }
    for(int i = 0; i < n + 1; i++) cout << ans[i] << ' ';
                 
        
                 
    
    return 0;
}

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