Submission #573116

#TimeUsernameProblemLanguageResultExecution timeMemory
573116tekiJust Long Neckties (JOI20_ho_t1)C++11
100 / 100
215 ms31088 KiB
#include <bits/stdc++.h> typedef long long ll; #define pb push_back #define MS(x,y) memset((x),(y),sizeof((x))) #define MN 1000000007 using namespace std; vector<pair<bool,int>> pref[200005]; multiset<int> pos; int main() { #if LOCAL_DEBUG fstream cin("in.txt"); #endif ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n; cin>>n; pair<int,int> niza[n+1]; for (int i = 0; i<n+1; i++) cin>>niza[i].first; for (int i = 0; i<n+1; i++) niza[i].second = i; int init[n]; for (int i = 0; i<n; i++) cin>>init[i]; sort(niza,niza+(n+1)); sort(init,init+n); for (int i = 0; i<n; i++) { int br = init[i]; int prv = niza[i].first; int vtor = niza[i+1].first; if (vtor-br > 0) { pref[0].pb({1,vtor-br}); pref[i+1].pb({0,vtor-br}); } if (prv-br > 0) { pref[i+1].pb({1,prv-br}); } } int res[n+1]; MS(res,0); for (int i = 0; i<n+1; i++) { sort(pref[i].rbegin(),pref[i].rend()); for (auto it:pref[i]) { if (it.first == 0) pos.erase(pos.find(it.second)); else pos.insert(it.second); } if (pos.size() == 0) continue; auto orel = pos.end(); orel--; res[niza[i].second] = *orel; } for (int i = 0; i<n+1; i++) cout<<res[i]<<" "; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...