Submission #1040783

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040783		joelgun14	Just Long Neckties (JOI20_ho_t1)	C++17	100 / 100	60 ms	11088 KiB

ho_t1

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define endl "\n"
#define ll long long
#define mp make_pair
#define ins insert
#define lb lower_bound
#define pb push_back
#define ub upper_bound
#define lll __int128
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
int main() {
  ios_base::sync_with_stdio(0); cin.tie(NULL);
  int n;
  cin >> n;
  pair<int, int> a[n + 2];
  int b[n + 1], pref[n + 1], suff[n + 3];
  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];
  pref[0] = suff[n + 2] = 0;
  sort(b + 1, b + n + 1);
  sort(a + 1, a + n + 2);
  for(int i = 1; i <= n; ++i) {
    pref[i] = max(pref[i - 1], max(0, a[i].fi - b[i]));
  }
  for(int i = n + 1; i >= 2; --i) {
    suff[i] = max(suff[i + 1], max(0, a[i].fi - b[i - 1]));
  }
  int ans[n + 2];
  for(int i = 1; i <= n + 1; ++i)
    ans[a[i].se] = max(pref[i - 1], suff[i + 1]);
  for(int i = 1; i <= n + 1; ++i)
    cout << ans[i] << " ";
  cout << endl;
  return 0;
}

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