Submission #536995

#	Time	Username	Problem	Language	Result	Execution time	Memory
536995		ddy888	Just Long Neckties (JOI20_ho_t1)	C++17	100 / 100	407 ms	62268 KiB

ho_t1

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define si second
#define ll long long 
#define int ll 
typedef pair<int,int> pi;

#ifdef LOCAL
#define debug(...) __f(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) 69
#endif
template <typename Arg>
void __f(string name, Arg arg) {
	cerr << name << " = " << arg << endl;
}
template <typename Head, typename... Tail>
void __f(string names, Head head, Tail... tail) {
	string cur = "";
	for (auto ch: names){if(ch==','){break;}else{cur+=ch;}}
	string nxt = names.substr(cur.size()+2);
	cerr << cur << " = " << head << ", ";
	__f(nxt, tail...);
}

const int mxn = 200005;
int N, B[mxn], ans[mxn];
pi A[mxn];

struct node {
	int s,e,m,v,lazy;
	node *l,*r;
	node (int _s, int _e) {
		s = _s, e = _e, m = (s+e)>>1;
		v = 0, lazy = 0;
		if (s!=e) {
			l = new node(s,m);
			r = new node(m+1,e);
		}
	}
	int prop() {
		if (s==e) {
			v += lazy;
			lazy = 0;
			return v;
		}
		v += lazy;
		r->lazy += lazy, l->lazy += lazy;
		lazy = 0;
		return v;
	}
	void update(int qs, int qe, int nv) {
		if (s==qs&&e==qe) lazy += nv;
		else {
			if (qe<=m) l->update(qs,qe,nv);
			else if (qs>m) r->update(qs,qe,nv);
			else l->update(qs,m,nv), r->update(m+1,qe,nv);
			v = max(l->prop(),r->prop());
		}
	}
	int query(int qs, int qe) {
		prop();
		if (qs==s&&qe==e) return prop();
		if (qs>m) return r->query(qs,qe);
		else if (qe<=m) return l->query(qs,qe);
		else return max(l->query(qs,m),r->query(m+1,qe));
	}
} *st[2];

int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> N;
	for (int i = 1; i <= N + 1; ++i) cin >> A[i].fi, A[i].si = 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 = 0; i < 2; ++i) st[i] = new node(1, N);
	for (int i = 1; i <= N; ++i) {
		st[0]->update(i, i, A[i].fi - B[i]);
		st[1]->update(i, i, A[i + 1].fi - B[i]);
	}
	for (int i = 1; i <= N + 1; ++i) {
		int idx = A[i].si, lx = 0, rx = 0;
		if (i != 1) lx = st[0]->query(1, i - 1);
		if (i != N + 1) rx = st[1]->query(i, N);
		ans[idx] = max(lx, rx);
	}
	for (int i = 1; i <= N + 1; ++i) cout << ans[i] << ' ';
	return 0;
}

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