Submission #867620

#	Time	Username	Problem	Language	Result	Execution time	Memory
867620		NeroZein	Constellation 3 (JOI20_constellation3)	C++17	100 / 100	318 ms	60436 KiB

constellation3

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

#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif

const int N = 2e5 + 5; 

int a[N]; 
int x[N], y[N], c[N]; 

int leaf[N]; 
int L[N], R[N]; 
long long dp[N];
int prop[N * 2];
vector<int> g[N];
long long tree[N];
vector<int> in_col[N]; 
int cnt, in[N], out[N];
vector<pair<int, int>> vec[N]; 
map<pair<int, int>, vector<pair<int, int>>> mp; 

int search(vector<int>& mono, int v) {
  int lo = 0, hi = (int) mono.size() - 1;
  while (lo < hi) {
    int mid = (lo + hi + 1) / 2; 
    if (a[mono[mid]] >= v) lo = mid;
    else hi = mid - 1; 
  }
  return mono[lo]; 
}

void assign(int nd, int l, int r, int s, int e, int v) {
  if (l >= s && r <= e) {
    prop[nd] = min(prop[nd], v); 
    return; 
  }
  int mid = (l + r) >> 1;
  int rs = nd + ((mid - l + 1) << 1);
  if (mid >= e) {
    assign(nd + 1, l, mid, s, e, v); 
  } else {
    if (mid < s) {
      assign(rs, mid + 1, r, s, e, v); 
    } else {      
      assign(nd + 1, l, mid, s, e, v); 
      assign(rs, mid + 1, r, s, e, v); 
    }
  }
}

int get(int nd, int l, int r, int p) {
  int ret = prop[nd];
  if (l == r) {
    return ret;
  }
  int mid = (l + r) >> 1;
  int rs = nd + ((mid - l + 1) << 1);
  if (p <= mid) {
    return min(ret, get(nd + 1, l, mid, p)); 
  } else {
    return min(ret, get(rs, mid + 1, r, p)); 
  }
}

void pre(int v) {
  in[v] = cnt++; 
  for (int u : g[v]) {
    pre(u); 
  }
  //deb(v) deb(in[v]) cout << '\n';
  out[v] = cnt - 1; 
}

void upd(int i, long long v) {
  ++i;
  while (i < N) {
    tree[i] += v; 
    i += i & -i; 
  }
}

long long qry(int i) {
  ++i;
  long long ret = 0;
  while (i) {
    ret += tree[i];
    i -= i & -i; 
  }
  return ret;
}

void dfs(int v) {
  for (int u : g[v]) {
    dfs(u);
    dp[v] += dp[u]; 
  }
  for (int u : g[v]) {
    upd(in[v], dp[u]); upd(out[v] + 1, -dp[u]);
    upd(in[u], -dp[u]); upd(out[u] + 1, dp[u]); 
  }
  for (auto [val, col] : vec[v]) {
    int pos = in[leaf[col]]; 
    dp[v] = max(dp[v], val + qry(pos)); 
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i]; 
  }
  int m;
  cin >> m;
  long long ans = 0;
  for (int i = 1; i <= m; ++i) {
    cin >> x[i] >> y[i] >> c[i];
    in_col[x[i]].push_back(i); 
    ans += c[i]; 
  }
  vector<int> stk;
  stk.push_back(0); 
  a[0] = INT_MAX; 
  for (int i = 1; i <= n; ++i) {
    while (a[stk.back()] < a[i]) {
      stk.pop_back(); 
    }
    for (int j : in_col[i]) {
      L[j] = search(stk, y[j]) + 1; 
    }
    stk.push_back(i); 
  }
  stk.resize(1);
  stk[0] = n + 1; 
  a[n + 1] = INT_MAX;
  for (int i = n; i >= 1; --i) {
    while (a[stk.back()] < a[i]) {
      stk.pop_back();
    }
    for (int j : in_col[i]) {
      R[j] = search(stk, y[j]) - 1; 
    }
    stk.push_back(i); 
  }
  for (int i = 1; i <= m; ++i) {
    mp[make_pair(L[i], R[i])].emplace_back(c[i], x[i]); 
  }
  vector<pair<int, int>> ranges;
  for (auto i : mp) {
    ranges.push_back(i.first); 
  }
  sort(ranges.begin(), ranges.end(), [&](pair<int, int> i, pair<int, int> j) {
    return i.second - i.first < j.second - j.first; 
  });
  set<pair<int, int>> active;
  memset(prop, 63, sizeof prop); 
  for (int i = 0; i < (int) ranges.size(); ++i) {
    while (true) {
      auto it = active.lower_bound(make_pair(ranges[i].first, -1));
      if (it != active.end() && it -> first <= ranges[i].second) {
        g[i].push_back(it -> second);
        active.erase(it);
      } else {
        break; 
      }
    }
    vec[i] = mp[ranges[i]]; 
    active.emplace(ranges[i].first, i); 
    assign(0, 1, n, ranges[i].first, ranges[i].second, i); 
  }
  for (auto it : active) {
    g[n].push_back(it.second); 
  }
  assign(0, 1, n, 1, n, n); 
  for (int i = 1; i <= n; ++i) {
    leaf[i] = get(0, 1, n, i);
  }
  pre(n); 
  dfs(n);
  ans -= dp[n];
  cout << ans << '\n'; 
  return 0;
}

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