test/yukicoder/913.monotone_minima.test.cpp

• View this file on GitHub
• Last update: 2024-09-01 13:40:30+09:00
• Problem: https://yukicoder.me/problems/no/913

Depends on

• monotone minima (src/Optimization/monotone_minima.hpp)

Code

// competitive-verifier: PROBLEM https://yukicoder.me/problems/no/913
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#include <vector>
#include "src/Optimization/monotone_minima.hpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N;
 cin >> N;
 long long A[N], sum[N + 1];
 sum[0]= 0;
 for (int i= 0; i < N; ++i) cin >> A[i], sum[i + 1]= sum[i] + A[i];
 auto f= [&](int i, int j) { return (long long)(j - i) * (j - i) + sum[j] - sum[i]; };
 static constexpr long long INF= 1e18;
 vector<long long> ans(N, INF);
 auto rec= [&](auto rec, int L, int R) -> void {
  if (L == R) return;
  int M= (L + R) / 2;
  {
   auto select= [&](int i, int j, int k) { return f(L + i, M + 1 + j) > f(L + i, M + 1 + k); };
   auto r= monotone_minima(M - L, R - M, select);
   long long mn= INF;
   for (int i= L; i < M; ++i) {
    mn= min(mn, f(i, r[i - L] + M + 1));
    ans[i]= min(ans[i], mn);
   }
  }
  {
   auto select= [&](int i, int j, int k) { return f(L + j, M + 1 + i) > f(L + k, M + 1 + i); };
   auto l= monotone_minima(R - M, M + 1 - L, select);
   long long mn= INF;
   for (int i= R; i-- > M;) {
    mn= min(mn, f(l[i - M] + L, i + 1));
    ans[i]= min(ans[i], mn);
   }
  }
  rec(rec, L, M), rec(rec, M + 1, R);
 };
 rec(rec, 0, N);
 for (int i= 0; i < N; ++i) cout << ans[i] << '\n';
 return 0;
}

#line 1 "test/yukicoder/913.monotone_minima.test.cpp"
// competitive-verifier: PROBLEM https://yukicoder.me/problems/no/913
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#include <vector>
#line 3 "src/Optimization/monotone_minima.hpp"
// select(i,j,k) -> true if (i,k) is better than (i,j)
template <typename F> std::vector<int> monotone_minima(int H, int W, const F &select) {
 std::vector<int> ret(H);
 auto rec= [&](auto &rec, int h1, int h2, int w1, int w2) -> void {
  if (h1 == h2) return;
  int h= (h1 + h2) / 2, best_w= w1;
  for (int w= w1 + 1; w < w2; ++w)
   if (select(h, best_w, w)) best_w= w;
  ret[h]= best_w, rec(rec, h1, h, w1, best_w + 1), rec(rec, h + 1, h2, best_w, w2);
 };
 return rec(rec, 0, H, 0, W), ret;
}
#line 7 "test/yukicoder/913.monotone_minima.test.cpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N;
 cin >> N;
 long long A[N], sum[N + 1];
 sum[0]= 0;
 for (int i= 0; i < N; ++i) cin >> A[i], sum[i + 1]= sum[i] + A[i];
 auto f= [&](int i, int j) { return (long long)(j - i) * (j - i) + sum[j] - sum[i]; };
 static constexpr long long INF= 1e18;
 vector<long long> ans(N, INF);
 auto rec= [&](auto rec, int L, int R) -> void {
  if (L == R) return;
  int M= (L + R) / 2;
  {
   auto select= [&](int i, int j, int k) { return f(L + i, M + 1 + j) > f(L + i, M + 1 + k); };
   auto r= monotone_minima(M - L, R - M, select);
   long long mn= INF;
   for (int i= L; i < M; ++i) {
    mn= min(mn, f(i, r[i - L] + M + 1));
    ans[i]= min(ans[i], mn);
   }
  }
  {
   auto select= [&](int i, int j, int k) { return f(L + j, M + 1 + i) > f(L + k, M + 1 + i); };
   auto l= monotone_minima(R - M, M + 1 - L, select);
   long long mn= INF;
   for (int i= R; i-- > M;) {
    mn= min(mn, f(l[i - M] + L, i + 1));
    ans[i]= min(ans[i], mn);
   }
  }
  rec(rec, L, M), rec(rec, M + 1, R);
 };
 rec(rec, 0, N);
 for (int i= 0; i < N; ++i) cout << ans[i] << '\n';
 return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++-13	01_sample_01	AC	6 ms	4 MB
g++-13	01_sample_02	AC	5 ms	4 MB
g++-13	01_sample_03	AC	5 ms	4 MB
g++-13	02_random_01	AC	6 ms	4 MB
g++-13	02_random_02	AC	6 ms	4 MB
g++-13	02_random_03	AC	6 ms	4 MB
g++-13	02_random_04	AC	6 ms	4 MB
g++-13	02_random_05	AC	6 ms	4 MB
g++-13	03_random_01	AC	141 ms	9 MB
g++-13	03_random_02	AC	137 ms	8 MB
g++-13	03_random_03	AC	137 ms	8 MB
g++-13	03_random_04	AC	144 ms	8 MB
g++-13	03_random_05	AC	146 ms	9 MB
g++-13	04_random_01	AC	141 ms	9 MB
g++-13	04_random_02	AC	136 ms	8 MB
g++-13	04_random_03	AC	135 ms	8 MB
g++-13	05_random_01	AC	137 ms	9 MB
g++-13	05_random_02	AC	133 ms	8 MB
g++-13	05_random_03	AC	136 ms	8 MB
g++-13	06_random_01	AC	147 ms	9 MB
g++-13	06_random_02	AC	146 ms	9 MB
g++-13	06_random_03	AC	145 ms	9 MB
g++-13	06_random_04	AC	143 ms	9 MB
g++-13	06_random_05	AC	140 ms	9 MB
g++-13	06_random_06	AC	137 ms	9 MB
g++-13	06_random_07	AC	136 ms	9 MB
g++-13	06_random_08	AC	147 ms	9 MB
g++-13	06_random_09	AC	147 ms	9 MB
g++-13	07_random_01	AC	145 ms	9 MB
g++-13	07_random_02	AC	145 ms	9 MB
g++-13	07_random_03	AC	146 ms	9 MB
g++-13	08_random_01	AC	167 ms	9 MB
g++-13	08_random_02	AC	146 ms	9 MB
g++-13	08_random_03	AC	152 ms	9 MB
g++-13	09_random_01	AC	143 ms	9 MB
g++-13	09_random_02	AC	143 ms	9 MB
g++-13	09_random_03	AC	138 ms	9 MB
clang++-18	01_sample_01	AC	6 ms	4 MB
clang++-18	01_sample_02	AC	5 ms	4 MB
clang++-18	01_sample_03	AC	5 ms	4 MB
clang++-18	02_random_01	AC	6 ms	4 MB
clang++-18	02_random_02	AC	6 ms	4 MB
clang++-18	02_random_03	AC	6 ms	4 MB
clang++-18	02_random_04	AC	6 ms	4 MB
clang++-18	02_random_05	AC	5 ms	4 MB
clang++-18	03_random_01	AC	102 ms	9 MB
clang++-18	03_random_02	AC	104 ms	8 MB
clang++-18	03_random_03	AC	104 ms	8 MB
clang++-18	03_random_04	AC	102 ms	8 MB
clang++-18	03_random_05	AC	106 ms	9 MB
clang++-18	04_random_01	AC	97 ms	9 MB
clang++-18	04_random_02	AC	95 ms	8 MB
clang++-18	04_random_03	AC	93 ms	8 MB
clang++-18	05_random_01	AC	94 ms	9 MB
clang++-18	05_random_02	AC	95 ms	8 MB
clang++-18	05_random_03	AC	96 ms	8 MB
clang++-18	06_random_01	AC	94 ms	9 MB
clang++-18	06_random_02	AC	94 ms	9 MB
clang++-18	06_random_03	AC	111 ms	9 MB
clang++-18	06_random_04	AC	110 ms	9 MB
clang++-18	06_random_05	AC	102 ms	9 MB
clang++-18	06_random_06	AC	90 ms	9 MB
clang++-18	06_random_07	AC	92 ms	9 MB
clang++-18	06_random_08	AC	101 ms	9 MB
clang++-18	06_random_09	AC	102 ms	9 MB
clang++-18	07_random_01	AC	106 ms	9 MB
clang++-18	07_random_02	AC	107 ms	9 MB
clang++-18	07_random_03	AC	109 ms	9 MB
clang++-18	08_random_01	AC	98 ms	9 MB
clang++-18	08_random_02	AC	100 ms	9 MB
clang++-18	08_random_03	AC	106 ms	9 MB
clang++-18	09_random_01	AC	97 ms	9 MB
clang++-18	09_random_02	AC	95 ms	9 MB
clang++-18	09_random_03	AC	91 ms	9 MB

Back to top page