oj.uz

답안 #762975

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
762975 2023-06-22T02:00:11 Z vjudge1 Just Long Neckties (JOI20_ho_t1) C++14
0 / 100
 0 ms 340 KB 
#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 << v[i].second << " ";
//	}
//	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++) {
		if (v[i].second==0) {
			ans.push_back({v[i].second,get(1,1,n,1,n,1)});
			continue;
		}
		if (v[i].second==n) {
			ans.push_back({v[i].second,get(1,1,n,1,n,0)});
			continue;
		}
		ans.push_back({v[i].second,max(get(1,1,n,1,v[i].second,0),get(1,1,n,v[i].second+1,n,1))});
	}
	sort(ans.begin(),ans.end());
	for (int i = 0; i<=n; i++) {
		cout << ans[i].second << " ";
	}
}
signed main(){
	ios_base::sync_with_stdio(false); 
	cin.tie(0);
	cout.tie(0);
	solve();
}

Subtask #1
0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 91.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -