제출 #218136

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
218136		fedoseevtimofey	별자리 3 (JOI20_constellation3)	C++14	100 / 100	903 ms	77948 KiB

constellation3

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <iomanip>
#include <functional>
#include <cassert>

using namespace std;

typedef long long ll;

const int N = 2e5 + 7;

int p[N];
int l[N], r[N];
int el[N], er[N];

int get(int a) {
  return (a == p[a] ? a : p[a] = get(p[a]));
}

void join(int a, int b) {
  a = get(a);
  b = get(b);
  p[a] = b;
  l[b] = min(l[b], l[a]);
  r[b] = max(r[b], r[a]);
}

int vert_l[N], vert_r[N];
vector <int> gs[N];
vector <int> g[N];
ll cost[N];

struct Fenwick {
  vector <ll> f;
  int n;
  Fenwick(int _n) {
    n = _n;
    f.resize(n);
  }
  void modify(int i, ll val) {
    for (; i < n; i |= i + 1) {
      f[i] += val;
    }
  }
  void update(int l, int r, ll val) {
    modify(l, val);
    if (r + 1 < n) modify(r + 1, -val);
  }
  ll get(int r) {
    ll res = 0;
    for (; r >= 0; r &= r + 1, --r) {
      res += f[r];
    }
    return res;
  }
};

int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
#endif
  int n;
  cin >> n;
  vector <int> a(n);
  vector <vector <int>> nc(n);
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
    a[i] = n - a[i] - 1;
    if (a[i] != -1) {
      nc[a[i]].push_back(i);
    }
  }
  int m;
  cin >> m;
  vector <int> x(m), y(m);
  vector <vector <pair <int, int>>> who(n);
  vector <int> c(m);
  for (int i = 0; i < m; ++i) {
    cin >> y[i] >> x[i] >> c[i];
    --y[i];
    x[i] = n - x[i];
    who[x[i]].push_back({y[i], i});
  }            
  set <pair <int, int>> seg;
  map <pair <int, int>, int> num;
  int uk = 1;
  vector <int> have(n);
  for (int i = n - 1; i >= 0; --i) {
    for (auto j : nc[i]) {
      p[j] = j;
      l[j] = j;
      r[j] = j;
      have[j] = 1;
      if (j > 0 && have[j - 1]) {
        join(j, j - 1);
      }
      if (j + 1 < n && have[j + 1]) {
        join(j, j + 1);
      }
    }
    set <pair <int, int>> cur;
    for (auto pr : who[i]) {
      int id = pr.second;
      int yc = pr.first;
      int cl = l[get(yc)];
      int cr = r[get(yc)];
      if (cur.count({cl, cr})) {
        gs[num[{cl, cr}]].push_back(id);
      } else {
        cur.insert({cl, cr});
        while (true) {
          auto it = seg.lower_bound(make_pair(cl, -1));
          if (it != seg.end() && it->second <= cr) {
            g[uk].push_back(num[*it]);
            seg.erase(it);
          } else {
            break;
          }
        }
        vert_l[uk] = cl;
        vert_r[uk] = cr;
        gs[uk].push_back(id);
        num[{cl, cr}] = uk++;
      }
    } 
    for (auto p : cur) {
      seg.insert(p);
    }
  }
  vector <bool> rt(uk, true);
  for (int i = 1; i < uk; ++i) {
    for (int j : g[i]) {
      rt[j] = false;
    }
  }
  for (int i = 1; i < uk; ++i) {
    if (rt[i]) {
      g[0].push_back(i);
    }
  }
  vert_l[0] = 0, vert_r[0] = n - 1;
  vector <int> leaf(n);
  set <int> free;
  for (int i = 0; i < n; ++i) free.insert(i);
  vector <int> par(uk);
  vector <int> e;
  function <void(int, int)> dfs = [&] (int u, int p) {
    e.push_back(u);
    el[u] = (int)e.size() - 1;
    par[u] = p;
    for (auto v : g[u]) {
      dfs(v, u);
    }
    while (true) {
      auto it = free.lower_bound(vert_l[u]);
      if (it != free.end() && (*it) <= vert_r[u]) {
        leaf[*it] = u;
        free.erase(it);
      } else {
        break;
      }
    }
    er[u] = (int)e.size() - 1;
  };  
  dfs(0, -1);
  for (int i = 0; i < uk; ++i) {
    for (int id : gs[i]) {
      cost[i] += c[id];
    }
  }
  vector <vector <ll>> dp(uk, vector <ll> (2));
  vector <ll> sum(uk);
  Fenwick f1((int)e.size()), f2((int)e.size());
  auto get_vert = [&] (Fenwick &f, int v) {
    if (v == -1) return 0LL;
    return f.get(el[v]);
  };
  function <void(int)> zhfs = [&] (int u) {
    for (auto v : g[u]) {
      zhfs(v);
      sum[u] += min(dp[v][0], dp[v][1]);
    }
    dp[u][0] = sum[u] + cost[u];
    dp[u][1] = dp[u][0];
    f1.update(el[u], er[u], sum[u] + cost[u]);
    for (int id : gs[u]) {
      int l = leaf[y[id]];
      ll total = -c[id] + get_vert(f1, l) - get_vert(f1, par[u]) + get_vert(f2, l) - get_vert(f2, u);
      dp[u][1] = min(dp[u][1], total);
    }
    f2.update(el[u], er[u], -min(dp[u][0], dp[u][1]));
  };
  zhfs(0);
  cout << dp[0][0] << '\n';
}

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