Submission #207565

#	Time	Username	Problem	Language	Result	Execution time	Memory
207565		super_j6	Just Long Neckties (JOI20_ho_t1)	C++14	100 / 100	138 ms	32376 KiB

ho_t1

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
#define endl '\n'
#define pi pair<int, int>
#define f first
#define s second

const int maxn = 200001, k = 18;
int n;
pi a[maxn];
int b[maxn], lg[maxn];
int st[2][k][maxn];
int ans[maxn];

int mx(int t, int l, int r){
	if(l > r) return 0;
	int z = lg[r - l + 1];
	return max(st[t][z][l], st[t][z][r - (1 << z) + 1]);
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> n;
	
	for(int i = 0; i <= n; i++){
		cin >> a[i].f;
		a[i].s = i;
	}
	for(int i = 0; i < n; i++) cin >> b[i];
	
	sort(a, a + n + 1);
	sort(b, b + n);
	
	for(int i = 0; i < n; i++){
		st[0][0][i] = max(a[i].f - b[i], 0);
		st[1][0][i] = max(a[i + 1].f - b[i], 0);
	}
	
	for(int t = 0; t < 2; t++)
	for(int i = 1; i < k; i++)
	for(int j = 0; j + (1 << i) <= n; j++){
		st[t][i][j] = max(st[t][i - 1][j], st[t][i - 1][j + (1 << (i - 1))]);
	}
	
	lg[1] = 0;
	for(int i = 2; i <= n; i++) lg[i] = lg[i - 1] + (1 << (lg[i - 1] + 1) == i);
	
	for(int i = 0; i <= n; i++){
		ans[a[i].s] = max(mx(0, 0, i - 1), mx(1, i, n - 1));
	}
	
	cout << ans[0];
	for(int i = 1; i <= n; i++) cout << " " << ans[i];
	cout << endl;

	return 0;
}

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