Submission #762896

#	Time	Username	Problem	Language	Result	Execution time	Memory
762896		anhduc2701	Just Long Neckties (JOI20_ho_t1)	C++17	100 / 100	221 ms	18808 KiB

ho_t1

/*
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
*/
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define len(x) ll(x.size())
#define eb emplace_back
#define PI acos(-1.0)
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define BIT(x, i) (1 & ((x) >> (i)))
#define MASK(x) (1LL << (x))
#define task "tnc"
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i <= (n); i++)
typedef long long ll;
typedef long double ld;
const ll INF = 1e18;
const int maxn = 1e6 + 5;
const int mod = 1e9 + 7;
const int mo = 998244353;
using pi = pair<ll, ll>;
using vi = vector<ll>;
using pii = pair<pair<ll, ll>, ll>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n;
pair<int, int> a[maxn];
int b[maxn];
int ans[maxn];
signed main()
{
    cin.tie(0), cout.tie(0)->sync_with_stdio(0);
    cin >> n;
    for (int i = 1; i <= n + 1; i++)
    {
        cin >> a[i].fi;
        a[i].se = i;
    }
    for (int i = 1; i <= n; i++)
    {
        cin >> b[i];
    }
    sort(a + 1, a + 2 + n);
    sort(b + 1, b + 1 + n);
    multiset<int> d;
    for (int i = 1; i <= n; i++)
    {
        d.insert(max(0, a[i + 1].fi - b[i]));
    }
    ans[a[1].se] = *(d.rbegin());
    for (int i = 2; i <= n + 1; i++)
    {
        d.erase(d.find({max(0, a[i].fi - b[i - 1])}));
        d.insert(a[i - 1].fi - b[i - 1]);
        ans[a[i].se] = (*d.rbegin());
    }
    for (int i = 1; i <= n + 1; i++)
    {
        cout << ans[i] << " ";
    }
}

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