Submission #1159964

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159964		fryingduc	Constellation 3 (JOI20_constellation3)	C++20	100 / 100	250 ms	92668 KiB

constellation3

#include "bits/stdc++.h"

using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 2e5 + 5;
const int LG = 18;
int n, m, a[maxn];
int x[maxn], y[maxn], c[maxn];
pair<int, int> st[maxn][LG + 1];
vector<int> g[maxn];
int lg2[maxn];
int up[maxn][LG + 1], root;
vector<int> stars[maxn];
long long f[maxn];
long long fs[maxn];
int sz[maxn], head[maxn], h[maxn];
int tin[maxn], tout[maxn], rev[maxn], timer;

long long bit[maxn];

void update(int i, long long val) {
  for (; i <= n; i += i & (-i)) {
    bit[i] += val;
  }
}

long long get_sum(int i) {
  long long ans = 0;
  for (; i > 0; i -= i & (-i)) {
    ans += bit[i];
  }
  return ans;
}

long long get_sum(int l, int r) {
  return l > r ? 0 : get_sum(r) - get_sum(l - 1);
}

pair<int, int> get(int l, int r) {
  int p = lg2[r - l + 1];
  return min(st[l][p], st[r - (1 << p) + 1][p]);
}

int build_tree(int l, int r) {
  if (l > r) return -1;
  if (l == r) {
    sz[l] = 1;
    return l;
  }
  int mid = get(l, r).second;
  int lnd = build_tree(l, mid - 1), rnd = build_tree(mid + 1, r);
  sz[mid] = 1;
  if (lnd != -1) {
    sz[mid] += sz[lnd];
    up[lnd][0] = mid;
    g[mid].push_back(lnd);
  } 
  if (rnd != -1) {
    sz[mid] += sz[rnd];
    up[rnd][0] = mid;
    g[mid].push_back(rnd);
  }
  return mid;
}

void hld(int u) {
  if (!head[u]) {
    head[u] = u;
  }
  tin[u] = ++timer;
  rev[timer] = u;
  int big_child = -1;
  for (auto v:g[u]) {
    if (big_child == -1 || sz[big_child] < sz[v]) {
      big_child = v;
    }
  }
  if (big_child != -1) {
    h[big_child] = h[u] + 1;
    head[big_child] = head[u];
    hld(big_child);
  }
  for (auto v:g[u]) {
    if (v == big_child) continue;
    h[v] = h[u] + 1;
    hld(v);
  }
  tout[u] = timer;
}

long long get_path(int u, int v) {
  long long res = 0;
  while (head[u] != head[v]) {
    if (h[head[u]] > h[head[v]]) swap(u, v);
    res += get_sum(tin[head[v]], tin[v]);
    v = up[head[v]][0];
  }
  if (h[u] > h[v]) swap(u, v);
  res += get_sum(tin[u], tin[v]);
  return res;
}

void dfs(int u) {
  for (auto v:g[u]) {
    dfs(v);
    fs[u] += f[v];
  }
  f[u] = fs[u];
  update(tin[u], fs[u]);
  for (auto i:stars[u]) {
    int child = x[i];
    long long cur = c[i] + get_path(u, child);
    f[u] = max(f[u], cur);
//    debug(u, i, cur, get_path(u, child));
  }
//  debug(u, f[u]);
  update(tin[u], -f[u]);
}

void solve() {
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    st[i][0] = make_pair(n - a[i], i);
  }
  for (int j = 1; j <= LG; ++j) {
    for (int i = 1; i + (1 << j) <= n + 1; ++i) {
      st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
    }
  }
  root = build_tree(1, n);
  for (int i = 1; i <= LG; ++i) {
    for (int u = 1; u <= n; ++u) {
      up[u][i] = up[up[u][i - 1]][i - 1];
    }
  }
  cin >> m;
  long long sum = 0;
  for (int i = 1; i <= m; ++i) {
    cin >> x[i] >> y[i] >> c[i];
    int cur = x[i];
    for (int j = LG; j >= 0; --j) {
      if (up[cur][j] and a[up[cur][j]] < y[i]) {
        cur = up[cur][j];
      }
    }
    stars[cur].push_back(i);
    debug(cur, x[i], c[i]);
    sum += c[i];
  }
  hld(root);
  dfs(root);
  debug(sum, f[root]);
  cout << sum - f[root];
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  
  for (int i = 2; i < maxn; ++i) {
    lg2[i] = lg2[i >> 1] + 1;
  }

  solve();

  return 0;
}

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