Submission #203198

#	Time	Username	Problem	Language	Result	Execution time	Memory
203198		jovan_b	Just Long Neckties (JOI20_ho_t1)	C++17	100 / 100	237 ms	9592 KiB

ho_t1

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

typedef long long ll;
typedef long double ld;

pair <int, int> a[200005];
int b[200005];
int res[200005];
struct str{
    int val, lazy;
} seg[1000005];

void propagate(int node, int l, int r){
    seg[node].val = max(seg[node].val, seg[node].lazy);
    if(l == r) return;
    seg[node*2].lazy = max(seg[node*2].lazy, seg[node].lazy);
    seg[node*2+1].lazy = max(seg[node*2+1].lazy, seg[node].lazy);
}

void upd(int node, int l, int r, int tl, int tr, int val){
    propagate(node, l, r);
    if(tl > r || l > tr) return;
    if(tl <= l && r <= tr){
        seg[node].lazy = max(seg[node].lazy, val);
        propagate(node, l, r);
        return;
    }
    int mid = (l+r)/2;
    upd(node*2, l, mid, tl, tr, val);
    upd(node*2+1, mid+1, r, tl, tr, val);
}

int getval(int node, int l, int r, int x){
    propagate(node, l, r);
    if(l == r) return seg[node].val;
    int mid = (l+r)/2;
    if(x <= mid) return getval(node*2, l, mid, x);
    return getval(node*2+1, mid+1, r, x);
}

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;

	int n;
	cin >> n;
	for(int i=1; i<=n+1; i++){
        cin >> a[i].first;
        a[i].second = i;
	}
	for(int i=1; i<=n; i++) cin >> b[i];
	sort(a+1, a+1+n+1);
	sort(b+1, b+1+n);
	for(int i=1; i<=n; i++){\
        upd(1, 1, n+1, 1, i, max(0, a[i+1].first-b[i]));
        upd(1, 1, n+1, i+1, n+1, max(0, a[i].first-b[i]));
	}
	for(int i=1; i<=n+1; i++){
        res[a[i].second] = getval(1, 1, n+1, i);
	}
	for(int i=1; i<=n+1; i++) cout << res[i] << " ";
    return 0;
}

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