This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define all(vec) vec.begin(), vec.end()
#define ll long long
#define db double
#define pb push_back
#define pf push_front
#define newl "\n"
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define f first
#define s second
#define MOD 1000000007
using namespace std;
#pragma GCC diagnostic ignored "-Wunused-result"
void setIO(string name = "") {
ios_base::sync_with_stdio(0); cin.tie(0);
cout << fixed << setprecision(15);
if (name.size()) {
freopen((name+".in").c_str(), "r", stdin);
freopen((name+".out").c_str(), "w", stdout);
}
}
int main()
{
fast
//setIO("");
//freopen("filename.in", "r", stdin);
//freopen("filename.out", "w", stdout);
ll n; cin >> n;
vector <ll> nw(n + 1), init(n);
unordered_map <ll, vector <ll>> occ;
unordered_map <ll, ll> idx, ans;
for (ll i = 0; i <= n; i++)
{
cin >> nw[i];
occ[nw[i]].pb(i);
}
for (ll i = 0; i < n; i++) cin >> init[i];
sort(all(nw));
sort(all(init));
for (ll i = n; i >= 0; i--)
{
idx[i] = occ[nw[i]].back();
occ[nw[i]].pop_back();
}
priority_queue <pair <ll, pair <ll, ll>>> pq;
//cout << newl;
for (ll i = 1; i <= n; i++)
{
pq.push({max(nw[i] - init[i - 1], (ll) 0), {2, i}});
}
//cout << newl << newl;
for (ll i = 0; i <= n; i++)
{
if (i != 0)
{
pq.push({max(nw[i - 1] - init[i - 1], (ll) 0), {1, 0}});
while (pq.size() && pq.top().s.f == 2 && pq.top().s.s <= i)
{
pq.pop();
}
}
ans[idx[i]] = pq.top().f;
}
for (ll i = 0; i <= n; i++)
{
cout << ans[i] << ' ';
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |