Submission #1253578

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253578		LucaLucaM	Constellation 3 (JOI20_constellation3)	C++17	100 / 100	195 ms	74624 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>> changes(n + 1);

  changes[0][1] = 0;
  for (int i = 1; i <= n; i++) {
    changes[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 augment = [&](int u, int h, ll v) {
    if ((--changes[u].upper_bound(h)) -> second >= v) {
      return;
    }
    changes[u][h] = v;
    auto it = changes[u].upper_bound(h);
    while (it != changes[u].end() && it -> second <= v)  {
      it = changes[u].erase(it);
    }
  };

  std::vector<ll> offset(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 = offset[l] + (--changes[l].upper_bound(a[u])) -> second;
    ll dr = offset[r] + (--changes[r].upper_bound(a[u])) -> second;

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

    if (changes[l].size() > changes[r].size())  {
      std::swap(l, r);
    }
    if (r) {
      std::swap(changes[u], changes[r]);
      std::swap(offset[u], offset[r]);
    }
    offset[0] = 0;
    for (const auto &[h, v] : changes[l]) {
      augment(u, h, v + offset[l] - offset[u]);
    }
    for (const auto &[h, v] : stars[u]) {
      augment(u, h, v + st + dr - offset[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 -= offset[st[0]] + changes[st[0]].rbegin() -> second;
  std::cout << ret;
  
  return 0;
}

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