Submission #503848

#	Time	Username	Problem	Language	Result	Execution time	Memory
503848		cig32	Just Long Neckties (JOI20_ho_t1)	C++17	100 / 100	102 ms	15408 KiB

ho_t1

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
const int MAXN = 3e5 + 10;
const int MOD = 1e9 + 7;
#define int long long

int rnd(int x, int y) { // random number generator
  int u= uniform_int_distribution<int>(x, y)(rng); return u;
}

void solve(int tc) {
  int N;
  cin >> N;
  pair<int,int> A[N+2];
  for(int i=1; i<=N+1; i++){
    cin >> A[i].first;
    A[i].second = i;
  }
  sort(A+1, A+N+2);
  int B[N+1];
  for(int i=1; i<=N; i++)cin >> B[i];
  sort(B+1, B+N+1);
  int pre[N+1], suf[N+2];
  pre[0] = suf[N+1] = 0;
  for(int i=1; i<=N; i++) pre[i] = max(pre[i-1], A[i].first - B[i]);
  for(int i=N; i>=1; i--) suf[i] = max(suf[i+1], A[i+1].first - B[i]);
  int ans[N+2];
  for(int i=1; i<=N+1; i++) {
    ans[A[i].second] = max(pre[i-1], suf[i]);
  }
  for(int i=1; i<=N+1; i++) cout << ans[i] << " ";
  cout << "\n";
}

int32_t main(){
  ios::sync_with_stdio(0); cin.tie(0);
  int t = 1; //cin >> t;
  for(int i=1; i<=t; i++) solve(i);
}
/*
3 4 6 7
2 4 6
*/

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