Submission #1153316

#TimeUsernameProblemLanguageResultExecution timeMemory
1153316zhasynJust Long Neckties (JOI20_ho_t1)C++20
100 / 100
90 ms11660 KiB
#include <bits/stdc++.h> #define pb push_back #define pf push_front using namespace std; #define F first #define S second typedef long long ll; #define pii pair <int, int> #define pll pair <ll, ll> typedef long double ld; const ll N = 2 * 1e5 + 100, M = 4096 + 10, len = 21, inf = 1e18; const ll mod = 1e9 + 7; pll a[N]; ll b[N], pref[N], suff[N], pos[N]; int main(){ ios::sync_with_stdio(false); cin.tie(NULL); ll n; cin >> n; for(ll i = 0; i <= n; i++){ cin >> a[i].F; a[i].S = i; } for(ll i = 0; i < n; i++){ cin >> b[i]; } sort(a, a + n + 1); sort(b, b + n); for(ll i = 0; i < n; i++){ if(i > 0) pref[i] = pref[i - 1]; pref[i] = max(pref[i], a[i].F - b[i]); } for(ll i = n; i >= 1; i--){ suff[i] = suff[i + 1]; suff[i] = max(suff[i], a[i].F - b[i - 1]); } for(ll i = 0; i <= n; i++){ pos[a[i].S] = i; } ll ans = 0; for(ll i = 0; i <= n; i++){ if(pos[i] > 0) ans = pref[pos[i] - 1]; ans = max(ans, suff[pos[i] + 1]); cout << ans << " "; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...