Submission #219754

#	Time	Username	Problem	Language	Result	Execution time	Memory
219754		AlexPop28	Constellation 3 (JOI20_constellation3)	C++11	100 / 100	375 ms	37864 KiB

constellation3

#include <bits/stdc++.h>
#define dbg() cerr <<
#define name(x) (#x) << ": " << (x) << ' ' <<

using namespace std;

// sunt putin penal ca mergea aib
namespace SegmTree {
  int n;
  vector<int64_t> tree, lazy;

  void Init(int n_) {
    n = n_;
    tree.assign(4 * n, 0);
    lazy.assign(4 * n, 0);
  }

  void Push(int node) {
    if (lazy[node] == 0) return;
    for (int son : {2 * node + 1, 2 * node + 2}) {
      tree[son] += lazy[node];
      lazy[son] += lazy[node];
    }
    lazy[node] = 0;
  }

  void Add(int node, int left, int right, int x, int y, int64_t val) {
    if (x <= left && right <= y) {
      tree[node] += val;
      lazy[node] += val;
      return;
    }
    Push(node);
    int mid = left + (right - left) / 2;
    if (x <= mid)
      Add(2 * node + 1, left, mid, x, y, val);
    if (mid < y)
      Add(2 * node + 2, mid + 1, right, x, y, val);
  }

  int64_t Query(int node, int left, int right, int pos) {
    if (left == right) {
      return tree[node];
    }
    Push(node);
    int mid = left + (right - left) / 2;
    if (pos <= mid)
      return Query(2 * node + 1, left, mid, pos);
    else
      return Query(2 * node + 2, mid + 1, right, pos);
  }

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

  int64_t Query(int pos) {
    return Query(0, 0, n - 1, pos);
  }
}

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);

    // dbg() "Union: " << name(x) name(y) endl;

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

    SegmTree::Add(lft[x], rgt[x], dp[y]);
    SegmTree::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) {
    // dbg() "DSU Upd: " << name(x) name(val) endl;
    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;
  }

  // le sterg pe toate si incerc sa pastrez o suma cat mai mare

  DSU::Init(n);
  SegmTree::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 (int i = 0; i < n; ++i) {
      // dbg() name(i) name(DSU::Get(i)) endl;
    // }


    for (auto &star : stars[y]) {
      int x, c; tie(x, c) = star;
      DSU::Update(x, c + SegmTree::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