Submission #1253557

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253557		LucaLucaM	Constellation 3 (JOI20_constellation3)	C++17	100 / 100	200 ms	74732 KiB

constellation3

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <map>

using ll = long long;
#define debug(x) #x << " = " << x << '\n'

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);
 
  int n;
  std::cin >> n;

  std::vector<int> a(n);
  for (int i = 0; i < n; i++) {
    std::cin >> a[i];
  }
  a.insert(a.begin(), 0);

  int m;
  std::cin >> m;

  std::vector<std::vector<std::pair<int, int>>> stars(n + 1);
  
  for (int i = 0; i < m; i++) {
    int x, y, c;
    std::cin >> x >> y >> c;
    stars[x].push_back({y, c});
  }

  for (int i = 1; i <= n; i++) {
    std::sort(stars[i].begin(), stars[i].end());
  }

  std::vector<int> st;
  std::vector<int> lc(n + 1, 0), rc(n + 1, 0);

  std::vector<std::map<int, ll>> answer(n + 1);

  answer[0][1] = 0;
  for (int i = 1; i <= n; i++) {
    answer[i][1] = 0;
    while (!st.empty() && a[st.back()] < a[i])  {
      lc[i] = st.back();
      st.pop_back();
    }
    if (!st.empty()) {
      rc[st.back()] = i;
    }
    st.push_back(i);
  }

  auto add = [&](int u, int h, ll v) {
    if ((--answer[u].upper_bound(h)) -> second >= v) {
      return;
    }
    answer[u][h] = v;
    auto it = answer[u].upper_bound(h);
    while (it != answer[u].end() && it -> second <= v)  {
      it = answer[u].erase(it);
    }
  };

  std::vector<ll> dp(n + 1, 0);

  auto solve = [&](auto &&self, int u) {
    if (!u) {
      return;
    }
    int l = lc[u];
    int r = rc[u];
    self(self, l);
    self(self, r);

    ll st = dp[l] + (--answer[l].upper_bound(a[u])) -> second;
    ll dr = dp[r] + (--answer[r].upper_bound(a[u])) -> second;

    dp[l] += dr;
    dp[r] += st;

    if (answer[l].size() > answer[r].size())  {
      std::swap(l, r);
    }
    if (r) {
      std::swap(answer[u], answer[r]);
      std::swap(dp[u], dp[r]);
    }
    dp[0] = 0;
    for (const auto &[h, v] : answer[l]) {
      add(u, h, v + dp[l] - dp[u]);
    }
    for (const auto &[h, v] : stars[u]) {
      add(u, h, v + st + dr - dp[u]);
    }
  };  

  solve(solve, st[0]);
  ll ret = 0;
  for (int i = 1; i <= n; i++) {
    for (const auto &[y, c] : stars[i]) {
      ret += c;
    }
  }
  ret -= dp[st[0]] + (--answer[st[0]].end()) -> second;
  std::cout << ret;
  
  return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 65 / 65