| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 763009 | tpd2k | Just Long Neckties (JOI20_ho_t1) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// teddybear's code
// the one who loves NBP
// noe the second
// goal: 0 / 8
// get medal in APIO (like TKN)
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
// prob:
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#define FOR(i,n) for (int i = 0; i<n; i++)
using ll = long long;
using ull = unsigned long long;
ll n,m,t;
ll cnt = 0;
const int maxn = 1e5;
const ll mod = 1e9 + 7;
#define Y "YES"
#define N "NO"
bool visited[1005][1005];
int dist[1005][1005];
int w,h;
int fx[4] = {-1, 1, 0, 0};
int fy[4] = {0, 0, -1, 1};
queue <pair<int,int>> q;
ll b[mod];
pair<ll,ll> a[mod];
ll st[4 * mod + 5];
ll ans[4 * mod + 5];
void build (int id, int l, int r)
{
if (l == r)
{
st[id] = max(0LL, a[l+1].first - b[l]);
return;
}
int m = (l + r) / 2;
build(id*2,l,m);
build(id*2+1, m+1, r);
st[id] = max(st[id*2], st[id*2+1]);
}
void update(int id, int l, int r, int lq, int rq, int val)
{
if (l > rq || r < lq)
{
return;
}
if (l >= lq && r <= rq)
{
//cout << "!!" << ' ' << l << ' ' << r << ' ' << val << ' ' << b[l] << '\n';
st[id] = max(0LL, val - b[l]);
return;
}
int m = (l + r) / 2;
update(id*2,l,m,lq,rq,val);
update(id*2+1,m+1,r,lq,rq,val);
st[id] = max(st[id*2], st[id*2+1]);
}
void solve()
{
cin >> n;
for (int i = 1; i<=n+1; i++)
{
cin >> a[i].first;
a[i].second = i;
}
for (int i = 1; i<=n; i++)
{
cin >> b[i];
}
sort(a+1,a+n+2);
sort(b+1,b+n+1);
/*for (int i = 1; i<=n+1; i++)
{
cout << a[i].first << ' ' << a[i].second << '\n';
}*/
build(1,1,n);
ans[a[1].second] = st[1];
/*for (int i = 1; i<=2*n; i++)
{
cout << "! " << i << ' ' << st[i] << '\n';
}
return;*/
for (int i = 2; i<=n+1; i++)
{
//cout << a[i].first << '\n';
update(1,1,n,i-1,i-1,a[i-1].first);
//cout << st[1] << '\n';
/*for (int j = 1; j<=2*n; j++)
{
cout << "! " << j << ' ' << st[j] << '\n';
}*/
ans[a[i].second] = st[1];
}
for (int i = 1; i<=n+1; i++)
{
cout << ans[i] << ' ';
}
}
/*
3
4 3 7 6
2 6 4
*/
void init()
{
int te = 1;
while (te--)
{
solve();
}
}
void preprocess()
{
}
int main()
{
//ios_base::sync_with_stdio(false);
//cin.tie(NULL);
//cin.tie(0); cout.tie(0);
//freopen(".inp", "r", stdin);
//freopen(".out", "w", stdout);
init();
preprocess();
//solve();
return 0;
}