Submission #762915

#	Time	Username	Problem	Language	Result	Execution time	Memory
762915		cheat_when_I_was_young	Just Long Neckties (JOI20_ho_t1)	C++17	100 / 100	158 ms	11848 KiB

ho_t1

// #cheat_when_I_was_young
// #cheatkhitacontre #khionhatoicheat
// #thaycuckythatvong
#include "bits/stdc++.h"
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")
const int NM = 2e5 + 5;
int n, a[NM], b[NM], tmp1[NM], tmp2[NM], tree1[NM<<2], tree2[NM<<2], ans[NM];
pair<int,int> c[NM];
void build(int *tree, int *arr, int id = 1, int l = 1, int r = n) {
    if (l == r) {
        tree[id] = arr[l];
        return;
    }
    int mid = (l+r) >> 1;
    build(tree, arr, id<<1, l, mid);
    build(tree, arr, id<<1|1, mid+1, r);
    tree[id] = max(tree[id<<1], tree[id<<1|1]);
}
int get(int *tree, int u, int v, int id = 1, int l = 1, int r = n) {
    if (v < l || r < u) return 0;
    if (u <= l && r <= v) return tree[id];
    int mid = (l+r) >> 1;
    return max(get(tree, u, v, id<<1, l, mid), get(tree, u, v, id<<1|1, mid+1, r));
}
signed main() {
	IOS;
	cin >> n;
	for (int i = 1; i <= n+1; ++i) cin >> a[i];
	for (int i = 1; i <= n; ++i) cin >> b[i];
	for (int i = 1; i <= n+1; ++i) c[i] = {a[i], i};
	sort(a+1, a+n+2);
	sort(b+1, b+n+1);
    sort(c+1, c+n+2);
	for (int i = 1; i <= n; ++i) {
        tmp1[i] = max(a[i] - b[i], 0);
        tmp2[i] = max(a[i+1] - b[i], 0);
	}
    build(tree1, tmp1);
    build(tree2, tmp2);
    for (int i = 1; i <= n+1; ++i) {
        int x = c[i].second;
        if (i == 1) ans[x] = get(tree2, 1, n);
        else if (i == n+1) ans[x] = get(tree1, 1, n);
        else ans[x] = max(get(tree1, 1, i-1), get(tree2, i, n));
    }
    for (int i = 1; i <= n+1; ++i) cout << ans[i] << " \n"[i == n+1];
}

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