Submission #944227

#TimeUsernameProblemLanguageResultExecution timeMemory
944227wapasSplit the sequence (APIO14_sequence)C++14
0 / 100
26 ms10508 KiB
// code by wapas #include <bits/stdc++.h> using namespace std; typedef long long ll; struct CHT { const ll inf = 1e9; vector<pair<ll, ll>> lineStk = {}; vector<ll> pointStk = {}; vector<int> idxStk = {}; ll isMin = 1; void toggleMinMax() { isMin *= -1; } void add(ll a, ll b = 0, int idx = -1) { a *= isMin; b *= isMin; while (lineStk.size()) { auto [p, q] = lineStk.back(); if (a == p) { if (b > q) { lineStk.pop_back(); pointStk.pop_back(); idxStk.pop_back(); } else break; continue; } auto k = pointStk.back(); ll prev = p * k + q, curr = a * k + b; if (curr >= prev) { lineStk.pop_back(); pointStk.pop_back(); idxStk.pop_back(); } else { break; } } if (lineStk.size()) { auto [p, q] = lineStk.back(); if (a != p) { ll num = q - b, den = a - p; ll t = (num + den - 1) / den; lineStk.push_back({ a, b }); pointStk.push_back(t); idxStk.push_back(idx); } } else { lineStk.push_back({ a, b }); pointStk.push_back(-inf); idxStk.push_back(idx); } } ll query(ll t) { int l = 0, r = pointStk.size(); while (l + 1 < r) { int m = (l + r) / 2; if (pointStk[m] <= t) l = m; else r = m; } return l; } ll value(ll t, ll idx) { return (lineStk[idx].first * t + lineStk[idx].second) * isMin; } void replace(CHT &o) { swap(lineStk, o.lineStk); swap(pointStk, o.pointStk); swap(idxStk, o.idxStk); swap(isMin, o.isMin); } }; void solution(int t) { ll N, K; cin >> N >> K; vector<ll> S(N + 1); for (int i = 1; i <= N; i++) { ll x; cin >> x; S[i] = x; S[i] += S[i - 1]; } vector<ll> cache(N + 1, 0); vector<vector<int>> prev(K + 1, vector<int>(N + 1, -1)); CHT cht; for (int n = 1; n <= N; n++) cht.add(S[n], - S[n] * S[n], n - 1); for (int k = 1; k <= K; k++) { CHT ncht; vector<ll> ncache(N + 1, 0); for (int n = 1; n <= N; n++) { int i = cht.query(S[n]); ncache[n] = cht.value(S[n], i); prev[k][n] = cht.idxStk[i]; ncht.add(S[n], ncache[n] - S[n] * S[n], n - 1); } cht.replace(ncht); swap(cache, ncache); } vector<int> history = {}; int k = K, n = N; while (prev[k][n] != -1) { history.push_back(prev[k][n]); n = prev[k--][n]; } sort(history.begin(), history.end()); for (int i = 0; i < history.size(); i++) { if (history[i] == 0) history[i] = 1; if (i > 0 && history[i] <= history[i - 1]) history[i] = history[i - 1] + 1; } cout << (ll) cache[N] << "\n"; for (auto e : history) cout << e << " "; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); // int T; cin >> T; int T = 1; for (int t = 0; t < T; t++) { solution(t); } }

Compilation message (stderr)

sequence.cpp: In member function 'void CHT::add(ll, ll, int)':
sequence.cpp:20:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   20 |             auto [p, q] = lineStk.back();
      |                  ^
sequence.cpp:42:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   42 |             auto [p, q] = lineStk.back();
      |                  ^
sequence.cpp: In function 'void solution(int)':
sequence.cpp:108:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |     for (int i = 0; i < history.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...