Submission #763012

#	Time	Username	Problem	Language	Result	Execution time	Memory
763012		tpd2k	Just Long Neckties (JOI20_ho_t1)	C++14	100 / 100	221 ms	12580 KiB

ho_t1

// 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 = 1e6;
#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;
}

• Subtask 1: 1 / 1
• Subtask 2: 8 / 8
• Subtask 3: 91 / 91