Submission #244852

#	Time	Username	Problem	Language	Result	Execution time	Memory
244852		vioalbert	Just Long Neckties (JOI20_ho_t1)	C++14	100 / 100	216 ms	8808 KiB

ho_t1

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 2e5+5;
int n;
int b[N], odd[N], ans[N];
vector<pair<int, int>> a;

void read() {
	cin >> n;
	for(int i = 0; i <= n; i++) {
		int x; cin >> x;
		a.push_back({x, i});
	}
	sort(a.begin(), a.end());
	for(int i = 0; i < n; i++)
		cin >> b[i];
	sort(b, b+n);
}

//segment tree
int st[4*N];

void update(int idx, int l, int r, int x, int val) {
	if(r < x || x < l) return;
	if(l == r && l == x) {
		st[idx] = val;
		return;
	}
	int lc = idx<<1, rc = lc|1;
	update(lc, l, (l+r)/2, x, val);
	update(rc, (l+r)/2+1, r, x, val);
	st[idx] = max(st[lc], st[rc]);
}

int query(int idx, int l, int r, int x, int y) {
	if(r < x || y < l) return 0;
	else if(x <= l && r <= y) return st[idx];
	int lc = idx<<1, rc = lc|1;
	int lq = query(lc, l, (l+r)/2, x, y);
	int rq = query(rc, (l+r)/2+1, r, x, y);
	return max(lq, rq);
}

void solve() {
	memset(st, 0, sizeof st);
	for(int i = 0; i < n; i++)
		update(1, 0, n-1, i, max(0, a[i+1].first - b[i]));

	for(int i = 0; i < n; i++) {
		ans[a[i].second] = query(1, 0, n-1, 0, n-1);
		update(1, 0, n-1, i, max(0, a[i].first - b[i]));
	}
	ans[a[n].second] = query(1, 0, n-1, 0, n-1);

	for(int i = 0; i < n+1; i++)
		cout << ans[i] << " \n"[i==n];
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	read();
	solve();
	return 0;
}

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