Submission #1116629

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116629		Bzslayed	Just Long Neckties (JOI20_ho_t1)	C++17	100 / 100	185 ms	49992 KiB

ho_t1

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 

using namespace std;
using namespace __gnu_pbds; 

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#define ll long long
#define ull unsigned long long
#define ld long double
#define pll pair<ll, ll>
#define pii pair<int, int>
#define coutpair(p) cout << p.first << " " << p.second << "|"

template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

struct node{
	int s, e, m;
	int 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);
		}
	}

	void update(int x, int v){
		if (s == e) {val = v;}
		else {
			if (x <= m) {l->update(x, v);}
			else {r->update(x, v);}
			val = max(l->val,r->val);
		}
	}

	int query(int S, int E){
		if (s == S && e == E) {return val;}
		else if (E <= m) {return l->query(S, E);}
		else if (S >= m+1) {return r->query(S, E);}
		else {return max(l->query(S, m),r->query(m+1, E));}
	}
} *curdiff, *nextdiff;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    ll n; cin >> n;
    pll a[n+1]; ll b[n];
    ll ans[n+1];

    for (int i=0; i<n+1; i++){
        cin >> a[i].first;
        a[i].second = i;
    }
    for (int i=0; i<n; i++) cin >> b[i];
    sort(a, a+n+1);
    sort(b, b+n);

    curdiff = new node(0, n+5);
    nextdiff = new node(0, n+5);
    for (int i=0; i<n; i++){ 
        ll cdiff = max(a[i].first-b[i], (ll)0);
        ll ndiff = max(a[i+1].first-b[i], (ll)0);
        curdiff->update(i, cdiff);
        nextdiff->update(i, ndiff);
    }

    for (int i=0; i<n+1; i++){
        if (i == 0) ans[a[i].second] = nextdiff->query(0, n-1);
        else if (i == n) ans[a[i].second] = curdiff->query(0, n-1);
        else ans[a[i].second] = max(curdiff->query(0, i-1), nextdiff->query(i, n-1));
    }

    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