제출 #1038640

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1038640		juicy	별자리 3 (JOI20_constellation3)	C++17	100 / 100	228 ms	51284 KiB

constellation3

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 2e5 + 5, inf = 1e9 + 7;

int n, m;
int a[N], c[N], tin[N], tout[N];
long long ft[N], dp[N];
array<int, 2> s[4 * N], buc[4 * N];
vector<array<int, 2>> pt[N];

void bld1(int id = 1, int l = 1, int r = n) {
  if (l == r) {
    s[id] = {-a[l], l};
    return;
  }
  int md = (l + r) / 2;
  bld1(id * 2, l, md);
  bld1(id * 2 + 1, md + 1, r);
  s[id] = min(s[id * 2], s[id * 2 + 1]);
}

void bld2(int id = 1, int l = 1, int r = n) {
  if (l == r) {
    buc[id] = {pt[l].back()[0], l};
    return;
  }
  int md = (l + r) / 2;
  bld2(id * 2, l, md);
  bld2(id * 2 + 1, md + 1, r);
  buc[id] = min(buc[id * 2], buc[id * 2 + 1]);
}

array<int, 2> qry(int u, int v, array<int, 2> *tree, int id = 1, int l = 1, int r = n) {
  if (u <= l && r <= v) {
    return tree[id];
  }
  int md = (l + r) / 2;
  if (v <= md) {
    return qry(u, v, tree, id * 2, l, md);
  }
  if (md < u) {
    return qry(u, v, tree, id * 2 + 1, md + 1, r);
  }
  return min(qry(u, v, tree, id * 2, l, md), qry(u, v, tree, id * 2 + 1, md + 1, r));
}

void pop(int i, int id = 1, int l = 1, int r = n) {
  if (l == r) {
    pt[l].pop_back();
    assert(pt[l].size());
    buc[id] = {pt[l].back()[0], l};
    return;
  }
  int md = (l + r) / 2;
  if (i <= md) {
    pop(i, id * 2, l, md);
  } else {
    pop(i, id * 2 + 1, md + 1, r);
  }
  buc[id] = min(buc[id * 2], buc[id * 2 + 1]);
}

void up(int i, long long x) {
  for (; i <= n; i += i & -i) {
    ft[i] += x;
  }
}

void up(int l, int r, long long x) {
  up(l, x);
  up(r + 1, -x);
}

long long qry(int i) {
  long long res = 0;
  for (; i; i -= i & -i) {
    res += ft[i];
  }
  return res;
}

int timer;

int dfs(int l, int r, int p) {
  int u = qry(l, r, s)[1];
  tin[u] = ++timer;
  long long sum = 0;
  if (l < u) {
    sum += dp[dfs(l, u - 1, a[u])];
  }
  if (u < r) {
    sum += dp[dfs(u + 1, r, a[u])];
  }
  dp[u] = sum;
  while (1) {
    auto x = qry(l, r, buc);
    if (x[0] > p) {
      break;
    }
    int v = x[1], c = pt[x[1]].back()[1];
    pop(x[1]);
    dp[u] = max(dp[u], sum + qry(tin[v]) + c);
  }
  tout[u] = timer;
  up(tin[u], tout[u], sum - dp[u]);
  return u;
}

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

  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
  }
  bld1();
  cin >> m;
  long long tot = 0;
  for (int i = 1; i <= m; ++i) {
    int x, y; cin >> x >> y >> c[i];
    pt[x].push_back({y, c[i]});
    tot += c[i];
  }
  for (int i = 1; i <= n; ++i) {
    pt[i].push_back({inf, 0});
    sort(pt[i].rbegin(), pt[i].rend());
  }
  bld2();
  cout << tot - dp[dfs(1, n, 1e9)];
  return 0;
}

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