Submission #1122683

#TimeUsernameProblemLanguageResultExecution timeMemory
1122683SulAJust Long Neckties (JOI20_ho_t1)C++20
100 / 100
88 ms6984 KiB
#include <bits/stdc++.h> using namespace std; #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/assoc_container.hpp> //#pragma GCC target("popcnt") using namespace __gnu_pbds; using namespace std; using ordered_set = tree<int, null_type, less_equal<>, rb_tree_tag, tree_order_statistics_node_update>; #define popcount __builtin_popcountll signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int n; cin >> n; pair<int,int> a[n+1]; int b[n]; for (int i = 0; i <= n; i++) { cin >> a[i].first; a[i].second = i; } for (int& x : b) cin >> x; sort(a, a+n+1); sort(b, b+n); int pref[n], suff[n], ans[n+1]{}; pref[0] = max(0, a[0].first - b[0]); for (int i = 1; i < n; i++) { pref[i] = max(pref[i-1], a[i].first - b[i]); } suff[n-1] = max(0, a[n].first - b[n-1]); for (int i = n-2; i >= 0; i--) { suff[i] = max(suff[i+1], a[i+1].first - b[i]); } for (int i = 0; i <= n; i++) { int ind = a[i].second; if (i != 0) ans[ind] = max(ans[ind], pref[i-1]); if (i < n) ans[ind] = max(ans[ind], suff[i]); } for (int x : ans) cout << x << " "; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...