Submission #1269394

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269394		WH8	Just Long Neckties (JOI20_ho_t1)	C++20	100 / 100	124 ms	33436 KiB

ho_t1

#include <bits/stdc++.h>
using namespace std;
#define iloop(x, n) for (long long i = x; i < n; ++i)
#define jloop(x, n) for (long long j = x; j < n; ++j)
#define kloop(x, n) for (long long k = x; k < n; ++k)
#define dloop(x, n) for (long long d = x; d >= n; --d)
#define ll long long
#define pll pair<long long, long long>
#define pii pair<int, int>
#define vi vector<long long>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define int long long
#define debug(x) cout << #x << ": " << x << endl
#define FASTIO               \
    ios::sync_with_stdio(false); \
	cin.tie(0);              \
    cout.tie(0);


int n;
struct node{
	int s, e, m; 
	int mx = 0;
	int val;
	node *l, *r;
	node (int S, int E){
		s = S, e = E, m = (s+e)>>1;
		if (s != e){
			l = new node(s, m);
			r = new node(m+1, e);
		}
	}
	void update(int x, int v){
		if (s == e) {
			mx = v;
		}
		else{
			if (x <= m) l->update(x, v);
			else r->update(x, v);
			mx = max(l->mx, r->mx);
		}
	}
} *root;


int32_t main(){
	FASTIO
	cin >> n;
	vector<pll> v; 
	root = new node(1, n+1);
	iloop(0, n+1) {
		int a; cin >> a;
		v.pb(mp(a, i));
	}
	sort(v.begin(), v.end());
	vi em(n); iloop(0, n) cin >> em[i];
	sort(em.begin(), em.end());
	int ans[n+1];
	iloop(0, n){
		int diff = v[i+1].f - em[i];
		root->update(i+1, diff);
	}
	ans[v[0].s] = max(root->mx, 0ll);
	iloop(1, n+1){
		int diff = v[i-1].f - em[i-1];
		root->update(i, diff);
		ans[v[i].s] = max(root->mx, 0ll);
	}
	iloop(0, n+1) cout << ans[i] << " ";
}

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