Submission #203099

#	Time	Username	Problem	Language	Result	Execution time	Memory
203099		godwind	Just Long Neckties (JOI20_ho_t1)	C++14	9 / 100	1089 ms	6492 KiB

ho_t1

// O O O O O O O O O O O O O O O OO O OO O OO O O O TTCH O TTTCH O TTTCH O O O O
#pragma GCC optimize("Ofast")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx")
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
#include <cstdio>
#include <math.h>
#include <cmath>
#include <string>
#include <cstring>
#include <queue>
#include <deque>
// #include <random>
#include <iomanip>
#include <bitset>
#include <cassert>

using namespace std;

#define y1 y11
#define double long double
#define less less228
#define left left228
#define right right228
#define list list228



template<typename T> void uin(T &a, T b) {
    if (b < a) a = b;
}
template<typename T> void uax(T &a, T b) {
    if (b > a) a = b;
}


// random_device rnd;

// template<typename T> void shuffle(vector< T > &v) {
//     for (int i = 1; i < (int)v.size(); ++i) {
//         swap(v[rnd() % i], v[i]);
//     }
//     for (int i = (int)v.size() - 1; i; --i) {
//         swap(v[rnd() % i], v[i]);
//     }
// }

const int N = 200 * 1000 + 228;

int n;
pair<int, int> a[N];
int b[N];
int left[N], right[N];
int ans[N];

void aux(int l, int r, int x) {
    if (l == 1) {
        uax(right[r], x);
    }
    if (r == n + 1) {
        uax(left[l], x);
    }
}

void dodo() {
    for (int i = 1; i <= n + 1; ++i) {
        uax(left[i], left[i - 1]);
    }
    for (int i = n + 1; i; --i) {
        uax(right[i], right[i + 1]);
    }
    for (int i = 1; i <= n + 1; ++i) {
        ans[i] = max(left[i], right[i]);
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n + 1; ++i) {
        cin >> a[i].first;
        a[i].second = i;
    }
    // sort(a + 1, a + n + 2);
    for (int i = 1; i <= n; ++i) {
        cin >> b[i];
    }
    vector<int> c(n + 2);
    for (int x = 1; x <= n + 1; ++x) {
        vector<int> A;
        vector<int> B;
        for (int i = 1; i <= n + 1; ++i) {
            if (i != x) A.push_back(a[i].first);
            if (i <= n) B.push_back(b[i]);
        }
        sort(A.begin(), A.end());
        sort(B.begin(), B.end());
        c[x] = 0;
        for (int i = 0; i < n; ++i) {
            uax(c[x], A[i] - B[i]);
        }
    }
    for (int i = 1; i <= n + 1; ++i) {
        cout << c[i] << ' ';
    }
    cout << endl;
    // sort(b + 1, b + n + 1);
    // for (int i = 1; i <= n; ++i) {
    //     aux(a[i].second + 1, n + 1, a[i].first - b[i]);
    //     aux(1, a[i].second, a[i + 1].first - b[i]);
    // }
    // dodo();
    // for (int i = 1; i <= n + 1; ++i) {
    //     cout << ans[i] << ' ';
    // }
    // cout << '\n';
    return 0;
}
// RU_023


// 

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