Submission #964277

#	Time	Username	Problem	Language	Result	Execution time	Memory
964277		rolandpetrean	Constellation 3 (JOI20_constellation3)	C++17	100 / 100	545 ms	103500 KiB

constellation3

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

using ll = long long;
#define int ll // srry

#define endl '\n'
#define pb push_back
using pi = array<int, 2>;

// i want to maximize costs of full set, remove from total
// max(a[i..j]) < min(s[i].y, s[j].y)
/*
cartesian tree on maximums of a
consider i
dp[i] = dp[parent]

consider some star with x = i
if i pick this star, then i can't pick any star in my subtree with y > a[i]
maximums of ancestors are increasing

~~let p be the first ancestor with a[p] >= y~~
~~dp[i] = max(dp[i], max_to_root[p] + s.cost)~~

let p be the last ancestor with a[p] < y
i have like chains from x to p, each has a cost
i need to pick disjoint set of chains with max cost
each node of the tree has <=2 children
*/

const int LG = 19;

struct BIT {
  int n;
  vector<int> bit;
  
  void update(int i, int x) {
    for (; i <= n; i += (i & -i)) bit[i] += x;
  }
  void update(int st, int dr, int x) {
    update(st, x);
    update(dr + 1, -x);
  }
  int query(int i) {
    int ret = 0;
    for (; i > 0; i -= (i & -i)) ret += bit[i];
    return ret;
  }
  
  BIT(int n) {
    this->n = n;
    bit.assign(n + 1, 0);
  }
};

struct Star {
  int x, y, cost;
};

int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  
  int n;
  cin >> n;
  
  vector<int> a(n + 1);
  for (int i = 1; i <= n; ++i) cin >> a[i];
  a[0] = n + 1;
  
  int m;
  cin >> m;
  
  int total_cost = 0;
  vector<Star> stars(m);
  vector<vector<int>> stars_x(n + 1);
  for (int i = 0; i < m; ++i) {
    cin >> stars[i].x >> stars[i].y >> stars[i].cost;
    total_cost += stars[i].cost;
    stars_x[stars[i].x].pb(i);
  }
  
  vector<int> parent(n + 1);
  stack<int> st;
  for (int i = 1; i <= n; ++i) {
    while (!st.empty() && a[st.top()] < a[i]) st.pop();
    if (!st.empty()) parent[i] = st.top();
    st.push(i);
  }
  while (!st.empty()) st.pop();
  for (int i = n; i >= 1; --i) {
    while (!st.empty() && a[st.top()] <= a[i]) st.pop();
    if (!st.empty()) {
      if (a[st.top()] <= a[parent[i]]) parent[i] = st.top();
    }
    st.push(i);
  }
  
  vector<vector<int>> children(n + 1);
  for (int i = 1; i <= n; ++i) {
    children[parent[i]].pb(i);
  }
  
  BIT bit(2 * n + 5);
  
  int timer = 0;
  vector<vector<int>> chains(n + 1);
  vector<int> tin(n + 1), tout(n + 1);
  vector<vector<int>> up(n + 1, vector<int>(LG));
  function<void(int)> dfs = [&](int x) {
    tin[x] = ++timer;
    
    up[x][0] = parent[x];
    for (int h = 1; h < LG; ++h) {
      up[x][h] = up[up[x][h - 1]][h - 1];
    }
    
    for (int u : children[x]) dfs(u);
    
    for (int idx : stars_x[x]) {
      int p = x;
      for (int jmp = LG - 1; jmp >= 0; --jmp) {
        if (a[up[p][jmp]] < stars[idx].y) p = up[p][jmp];
      }
      
      chains[p].pb(idx);
    }
    
    tout[x] = ++timer;
  };
  dfs(0);
  
  // adj_dp - dp[i]
  vector<int> dp(n + 1);
  function<void(int)> dfs2 = [&](int x) {
    //cout << "IN " << x << endl;
    
    int adj_dp = 0;
    for (int u : children[x]) {
      dfs2(u);
      adj_dp += dp[u];
    }
    dp[x] = adj_dp;
    
    bit.update(tin[x], tout[x], adj_dp);
    
    for (int idx : chains[x]) {
      const Star& s = stars[idx];
      int cx = s.x;
      
      int cost = s.cost;
      cost += bit.query(tin[cx]);
      dp[x] = max(dp[x], cost);
      
      //cout << "CHAIN " << x << " -> " << cx << " | " << cost << endl;
    }
    
    bit.update(tin[x], tout[x], -dp[x]);
    
    //cout << "OUT " << x << " | " << dp[x] << endl;
  };
  dfs2(0);
  
  int max_cost = dp[0];
  int ans = total_cost - max_cost;
  cout << ans;
}

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