Submission #598137

#	Time	Username	Problem	Language	Result	Execution time	Memory
598137		cadmiumsky	Constellation 3 (JOI20_constellation3)	C++14	100 / 100	599 ms	78472 KiB

constellation3

#include <bits/stdc++.h>

using namespace std;
#define int ll
using ll = long long;
using pii = pair<int,int>;
const int nbit = 18, nmax = 2e5 + 5;

#define lsb(x) (x & -x)
struct AIB {
  vector<ll> tree; int len;
  void init(int n) {
    len = n;
    tree.clear(), tree.resize(n + 1, 0);
  }
  void upd(int x, int val) {
    while(x <= len) 
      tree[x] += val,
      x += lsb(x);
    return;
  }
  void upd(int l, int r, int val) {
    upd(l, val);
    upd(r + 1, -val);
  }
  int query(int x) {
    int sum = 0;
    while(x > 0) sum += tree[x], x -= lsb(x);
    return sum;
  }
};
int n, m;

namespace CartTree {
  vector<int> g[nmax];
  vector<pii> atrendpoint[nmax];
  int p[nmax][nbit], lson[nmax], rson[nmax], pin[nmax], pout[nmax], inp = 1;
  static int root;
  vector<int> v;
  ll dp[nmax], son[nmax];
  AIB pinexsum;
  
  void build(vector<int> abogus) {
    v = move(abogus);
    root = 0;
    for(int i = 0; i < n; i++) { //init carttree
      int lst = i - 1, lastval = -1;
      lson[i] = rson[i] = -1;
      while(lst >= 0 && v[lst] <= v[i])
        lastval = lst,
        lst = p[lst][0];
      p[i][0] = lst;
      lson[i] = lastval;
      if(lastval != -1)
        p[lastval][0] = i;
      if(lst != -1)
        rson[lst] = i;
    }
    for(int i = 0; i < n; i++) { // init tree
      if(lson[i] != -1)
        g[i].push_back(lson[i]),
        p[lson[i]][0] = i;
      if(rson[i] != -1)
        g[i].push_back(rson[i]),
        p[rson[i]][0] = i;
      if(p[i][0] == -1)
        root = i;
    }
    p[root][0] = root;
    for(int step = 1; step < nbit; step++)
      for(int i = 0; i < n; i++)
        p[i][step] = p[p[i][step - 1]][step - 1];
    auto dfs = [&](auto &&self, int node) -> void {
      pin[node] = inp++;
      for(auto x : g[node])
        self(self, x);
      pout[node] = inp - 1;
    };
    dfs(dfs, root);
    pinexsum.init(n + 1);
  }
  
  void addstar(int x, int height, int cost) {
    int temp = x;
    for(int i = nbit - 1; i >= 0; i--) {
      if(v[p[x][i]] < height)
        x = p[x][i];
    }
    atrendpoint[x].emplace_back(temp, cost);
  }
  
  void startdp(int node = root) {
    for(auto x : g[node])
      startdp(x),
      son[node] += dp[x];
    dp[node] = son[node];
    pinexsum.upd(pin[node], pout[node], son[node]);
    for(auto [x, cost] : atrendpoint[node])
      dp[node] = max(dp[node], (ll)cost + pinexsum.query(pin[x]));
    pinexsum.upd(pin[node], pout[node], -dp[node]);
  }
}

signed main() {
  cin >> n;
  vector<int> heights(n);
  for(auto &x : heights) 
    cin >> x;
  CartTree::build(heights);
  cin >> m;
  ll sum = 0;
  for(int i = 0, x, y, c; i < m; i++) {
    cin >> x >> y >> c;
    CartTree::addstar(x - 1, y, c);
    sum += c;
  }
  CartTree::startdp();
  cout << sum - CartTree::dp[CartTree::root] << '\n';
}
/*
 * 
 * 6   A 8   x 5
 *   x     x x x
 * x x     x x x
 * x x     x x x
 * x x 7 x x x x
 * x x x x x x x
 * x x x x x x x 
 * 
 * 
 */

Compilation message (stderr)

constellation3.cpp: In function 'void CartTree::startdp(ll)':
constellation3.cpp:98:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   98 |     for(auto [x, cost] : atrendpoint[node])
      |              ^

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