Submission #516960

#TimeUsernameProblemLanguageResultExecution timeMemory
516960kevinxiehkJust Long Neckties (JOI20_ho_t1)C++17
100 / 100
134 ms23412 KiB
#include <bits/stdc++.h> #define mp make_pair #define pb emplace_back #define fi first #define se second #define int long long #define ick cout<<"ickbmi32.9\n" using namespace std; bool isprime(int k) { for(int i = 2; i <= sqrt(k); i++) if(k % i == 0) return false; return true; } int bm(int a, int b, int mod) { if(b == 0) return 1; int t = bm(a, b / 2, mod); t = t * t % mod; return (b % 2 == 1 ? t * a % mod : t); } int inv(int a, int mod) {return bm(a, mod - 2, mod);} int ans[200005], aans[200005]; signed main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n; cin >> n; pair<int, int> arr[n + 5]; for(int i = 0; i <= n; i++) cin >> arr[i].fi, arr[i].se = i; int a[n + 5]; for(int i = 0; i < n; i++) cin >> a[i]; sort(a, a + n); sort(arr, arr + n + 1); vector<pair<int, pair<int, int>>> tm; // val, id, l/r for(int i = 0; i < n; i++) { tm.pb(mp(-max(arr[i].fi - a[i], 0LL), mp(i + 1, 0))); tm.pb(mp(-max(arr[i + 1].fi - a[i], 0LL), mp(i, 1))); } sort(tm.begin(), tm.end()); int lpt = 0, rpt = n; for(auto x: tm) { if(x.se.se == 0) { while(rpt >= x.se.fi) { ans[rpt] = max(ans[rpt], -x.fi); rpt--; } } else { while(lpt <= x.se.fi) { ans[lpt] = max(ans[lpt], -x.fi); lpt++; } } } for(int i = 0; i <= n; i++) aans[arr[i].se] = ans[i]; for(int i = 0; i <= n; i++) cout << aans[i] << (i == n ? '\n' : ' '); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...