Submission #566923

#TimeUsernameProblemLanguageResultExecution timeMemory
566923MrDebooJust Long Neckties (JOI20_ho_t1)C++17
100 / 100
334 ms22472 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define int long long #define endl '\n' using namespace std; using namespace __gnu_pbds; using ordered_set = tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>; signed main(){ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); int n; cin>>n; int arr[n+1]; for(auto &i:arr)cin>>i; int a[n+1]; for(int i=0;i<=n;i++)a[i]=arr[i]; sort(a,a+n+1); int b[n]; for(auto &i:b)cin>>i; sort(b,b+n); map<int,int>ans; int pre[n+1]; int suf[n+1]; for(int i=0;i<n;i++){ pre[i]=max(0ll,a[i]-b[i]); if(i)pre[i]=max(pre[i],pre[i-1]); } for(int i=n;i>=1;i--){ suf[i]=max(0ll,a[i]-b[i-1]); if(i!=n)suf[i]=max(suf[i],suf[i+1]); } for(int i=0;i<=n;i++){ if(i)ans[a[i]]=pre[i-1]; if(i!=n)ans[a[i]]=max(ans[a[i]],suf[i+1]); } for(int i=0;i<=n;i++)cout<<ans[arr[i]]<<' '; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...