Submission #253232

#	Time	Username	Problem	Language	Result	Execution time	Memory
253232		doowey	Just Long Neckties (JOI20_ho_t1)	C++14	100 / 100	128 ms	13176 KiB

ho_t1

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)2e5 + 10;
ll pf[N], sf[N];
ll ans[N];

int main(){
    fastIO;
    int n;
    cin >> n;
    vector<int> A(n);
    vector<pii> B(n + 1);
    for(int i = 0 ; i <= n; i ++ ){
        cin >> B[i].fi;
        B[i].se = i;
    }
    for(int i = 0 ; i < n ; i ++ ){
        cin >> A[i];
    }
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    for(int i = 0 ; i < n; i ++ ){
        pf[i]=max(B[i].fi-A[i],0);
        if(i>0)
            pf[i]=max(pf[i],pf[i-1]);
    }
    int q = n - 1;
    for(int i = B.size() - 1; i > 0 ; i -- ){
        sf[i] = max(B[i].fi-A[q],0);
        sf[i]=max(sf[i],sf[i+1]);
        q -- ;
    }
    ll cur;
    for(int i = 0 ; i < B.size(); i ++ ){
        cur = 0;
        if(i > 0) cur = max(cur, pf[i-1]);
        cur = max(cur, sf[i + 1]);
        ans[B[i].se] = cur;
    }
    for(int i = 0 ; i <= n; i ++ )
        cout << ans[i] << " ";
    cout << "\n";
    return 0;
}

Compilation message (stderr)

ho_t1.cpp: In function 'int main()':
ho_t1.cpp:44:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0 ; i < B.size(); i ++ ){
                     ~~^~~~~~~~~~

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