Submission #927221

#	Time	Username	Problem	Language	Result	Execution time	Memory
927221		Craftless	Just Long Neckties (JOI20_ho_t1)	C++17	100 / 100	207 ms	88920 KiB

ho_t1

#include <bits/stdc++.h>

#define int long long int
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define pi pair<int, int>
#define INF 1e13

using namespace std;

int N, A[200010], B[200010], ans[200010];
pi as[200010];


struct node {
    int s, e, m, val;
    node *l, *r;
    node (int _s, int _e) {
        s = _s; e = _e;
        m = (s + e) / 2;
        val = 0;
        if (s != e) {
            l = new node(s, m);
            r = new node(m + 1, e);
        }
    }
    
    int query(int _s, int _e) {
        if (s == _s and e == _e) {
            return val;
        }
        else if (_e <= m) {
            return l -> query(_s, _e);
        }
        else if (_s > m) {
            return r-> query(_s, _e);
        }
        else {
            return max(l -> query(_s, m), r -> query(m + 1, _e));
        }
    }
    
    void update(int p, int v) {
        if (s == p and e == p) {
            val = v;
        }
        else {
            if (p <= m) l -> update(p, v);
            else r -> update(p, v);
            val = max(l -> val, r -> val);
        }
        
    }

    void children() {
        if (s != e) {
            l = new node(s, m);
            r = new node(m + 1, e);
        }
    }

} *l, *r, *m;


int32_t main() {

	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	cin >> N;

	for (int i = 0; i < N + 1; i++) {
		cin >> A[i];
		as[i] = { A[i], i };
	}

	for (int i = 0; i < N; i++) {
		cin >> B[i];
	}
	l = new node(0, N - 1);
	m = new node(0, N - 1);
	r = new node(0, N - 1);

	sort(A, A + N + 1);
	sort(as, as + N + 1);
	sort(B, B + N);

	for (int i = 0; i < N; i++) {
		m -> update(i, max(A[i] - B[i], 0ll));
		r -> update(i, max(A[i + 1] - B[i], 0ll));
	}

	for (int i = 0; i < N + 1; i++) {
		int a = -INF, b = -INF;
		if (i - 1 >= 0) a = m -> query(0, i - 1);
		if (i <= N - 1) b = r -> query(i, N - 1);
		ans[as[i].S] = max(a, b);
	}

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





	return 0;	
}

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