Submission #219755

#	Time	Username	Problem	Language	Result	Execution time	Memory
219755		AlexPop28	Constellation 3 (JOI20_constellation3)	C++11	100 / 100	250 ms	26616 KiB

constellation3

#include <bits/stdc++.h>
using namespace std;

namespace Fenwick {
  int n;
  vector<int64_t> tree;

  void Init(int n_) {
    n = n_;
    tree.assign(n + 1, 0);
  }

  void Add(int pos, int64_t val) {
    for (++pos; pos <= n; pos += pos & -pos)
      tree[pos] += val;
  }

  void Add(int left, int right, int64_t val) {
    Add(left, val);
    if (right + 1 < n)
      Add(right + 1, -val);
  }

  int64_t Query(int pos) {
    int64_t res = 0;
    for (++pos; pos > 0; pos -= pos & -pos)
      res += tree[pos];
    return res;
  }
}

namespace DSU {
  int n;
  vector<int> dad, sz, lft, rgt;
  vector<int64_t> dp;

  void Init(int n_) {
    n = n_;
    dad.resize(n), sz.resize(n), lft.resize(n), rgt.resize(n), dp.resize(n);
    for (int i = 0; i < n; ++i) {
      lft[i] = rgt[i] = i;
      dad[i] = -1;
      sz[i] = 1;
      dp[i] = 0;
    }
  }

  int Find(int x) {
    if (dad[x] == -1) return x;
    return dad[x] = Find(dad[x]);
  }

  void Union(int x, int y) {
    x = Find(x), y = Find(y);
    if (x == y) return;
    if (sz[x] < sz[y]) swap(x, y);

    sz[x] += sz[y];
    dad[y] = x;

    Fenwick::Add(lft[x], rgt[x], dp[y]);
    Fenwick::Add(lft[y], rgt[y], dp[x]);

    dp[x] += dp[y];
    lft[x] = min(lft[x], lft[y]);
    rgt[x] = max(rgt[x], rgt[y]);
  }

  void Update(int x, int64_t val) {
    x = Find(x);
    dp[x] = max(dp[x], val);
  }

  int64_t Get(int node) {
    return dp[Find(node)];
  }
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  int n; cin >> n;
  vector<int> h(n);
  vector<vector<int>> walls(n + 1);
  for (int i = 0; i < n; ++i) {
    cin >> h[i];
    walls[h[i]].emplace_back(i);
  }
  
  int m; cin >> m;
  vector<vector<pair<int, int>>> stars(n + 1);
  int64_t ans = 0;
  for (int i = 0; i < m; ++i) {
    int x, y, c; cin >> x >> y >> c; --x, --y;
    stars[y].emplace_back(x, c);
    ans += c;
  }

  DSU::Init(n);
  Fenwick::Init(n);
  for (int y = 0; y <= n; ++y) {
    for (int &x : walls[y]) {
      if (x - 1 >= 0 && h[x - 1] <= y) {
        DSU::Union(x - 1, x);
      }
      if (x + 1  < n && h[x + 1] <= y) {
        DSU::Union(x, x + 1);
      }
    }

    for (auto &star : stars[y]) {
      int x, c; tie(x, c) = star;
      DSU::Update(x, c + Fenwick::Query(x));
    }
  }

  for (int i = 1; i < n; ++i) {
    DSU::Union(i - 1, i);
  }

  cout << ans - DSU::Get(0) << endl;
}

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