제출 #762992

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
762992		vjudge1	Just Long Neckties (JOI20_ho_t1)	C++14	100 / 100	174 ms	24132 KiB

ho_t1

#include<bits/stdc++.h>
#define int long long
#define BUG(x) cerr << #x << " = " << x << endl
using namespace std;
const int N = 200005;
int t,n,a[N],b[N],st[2][4*N],diff[2][N];
vector < pair < int , int > > v;
vector < pair < int , int > > ans;
void build(int id, int l, int r, int idx) {
	if (l>r) return;
	if (l==r) {
		st[idx][id] = diff[idx][l];
		return;
	}
	int m = (l+r)/2;
	build(id*2,l,m,idx);
	build(id*2+1,m+1,r,idx);
	st[idx][id] = max(st[idx][id*2],st[idx][id*2+1]);
}
int get(int id, int l, int r, int u, int v, int idx) {
	if (l>v || r<u) return 0;
	if (l>=u && r<=v) return st[idx][id];
	int m = (l+r)/2;
	return max(get(id*2,l,m,u,v,idx),get(id*2+1,m+1,r,u,v,idx));
}
void solve() {
	cin >> n;
	for (int i = 0; i<=n; i++) {
		cin >> a[i];
		v.push_back({a[i],i});
	}
	for (int i = 0; i<n; i++) {
		cin >> b[i];
	}
	sort(v.begin(),v.end());
	sort(a,a+n+1);
	sort(b,b+n);
//	for (int i = 0; i<n+1; i++) {
//		cout << a[i] << " ";
//	}
//	cout << endl;
//	for (int i = 0; i<n; i++) {
//		cout << b[i] << " ";
//	}
//	cout << endl;
	for (int i = 1; i<=n; i++) {
		diff[0][i] = max(a[i-1]-b[i-1],0LL);
		diff[1][i] = max(a[i]-b[i-1],0LL);
//		BUG(diff[0][i]);
//		BUG(diff[1][i]);
	}
	build(1,1,n,0);
	build(1,1,n,1);
	for (int i = 0; i<=n; i++) {
//		BUG(v[i].second);
//		BUG(v[i].first);
		if (i==0) {
			ans.push_back({v[i].second,get(1,1,n,1,n,1)});
//			BUG(ans[i].second);
			continue;
		}
		if (i==n) {
			ans.push_back({v[i].second,get(1,1,n,1,n,0)});
//			BUG(ans[i].second);
			continue;
		}
		ans.push_back({v[i].second,max(get(1,1,n,1,i,0),get(1,1,n,i+1,n,1))});
//		BUG(ans[i].second);
	}
	sort(ans.begin(),ans.end());
	for (int i = 0; i<=n; i++) {
//		BUG(ans[i].first);
		cout << ans[i].second << " ";
	}
}
signed main(){
	ios_base::sync_with_stdio(false); 
	cin.tie(0);
	cout.tie(0);
	solve();
}

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