Submission #684867

#	Time	Username	Problem	Language	Result	Execution time	Memory
684867		peijar	Constellation 3 (JOI20_constellation3)	C++17	35 / 100	1585 ms	118744 KiB

constellation3

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

string to_string(string s) { return s; }
template <typename T> string to_string(T v) {
  bool first = true;
  string res = "[";
  for (const auto &x : v) {
    if (!first)
      res += ", ";
    first = false;
    res += to_string(x);
  }
  res += "]";
  return res;
}

void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
  cout << ' ' << to_string(H);
  dbg_out(T...);
}

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

template <class T> struct RMQ {
  vector<vector<T>> jmp;
  RMQ(const vector<T> &V) : jmp(1, V) {
    for (int pw = 1, k = 1; pw * 2 <= (int)V.size(); pw *= 2, ++k) {
      jmp.emplace_back((int)V.size() - pw * 2 + 1);
      for (int j = 0; j < (int)jmp[k].size(); ++j)
        jmp[k][j] = max(jmp[k - 1][j], jmp[k - 1][j + pw]);
    }
  }
  T query(int a, int b) { // [a, b)
    assert(a < b);
    int dep = 31 - __builtin_clz(b - a);
    return max(jmp[dep][a], jmp[dep][b - (1 << dep)]);
  }
};

template <class T> class Fenwick {
public:
  int lim;
  vector<T> bit;

  Fenwick(int n) : lim(n + 1), bit(lim) {}

  void upd(int pos, T val) {
    for (pos++; pos < lim; pos += pos & -pos)
      bit[pos] += val;
  }

  T sum(int r) { // < r
    T ret = 0;
    for (; r; r -= r & -r)
      ret += bit[r];
    return ret;
  }

  T sum(int l, int r) { // [l, r)
    return sum(r) - sum(l);
  }

  void rangeAdd(int deb, int fin, int x) { // [deb, fin)
    dbg(deb, fin, x);
    upd(deb, x);
    upd(fin, -x);
  }

  int point(int pos) { return sum(pos + 1); }
};

template <class T> using min_pq = priority_queue<T, vector<T>, greater<T>>;

signed main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  int N;
  cin >> N;
  vector<int> height(N);
  for (int &x : height)
    cin >> x;
  vector<pair<int, int>> toRMQ;
  for (int i = 0; i < N; ++i)
    toRMQ.emplace_back(height[i], i);
  RMQ rmq(toRMQ);

  vector<vector<pair<int, int>>> onPos(N);
  int nbEtoiles;
  cin >> nbEtoiles;
  int totCost = 0;
  for (int i = 0; i < nbEtoiles; ++i) {
    int x, y, c;
    cin >> x >> y >> c;
    totCost += c;
    onPos[x - 1].emplace_back(y, c);
  }

  Fenwick<int> fen(N);

  auto DFS = [&](auto dfs, int deb, int fin,
                 int prevHeight) -> pair<min_pq<tuple<int, int, int>>, int> {
    auto [valMax, posMax] = rmq.query(deb, fin);
    min_pq<tuple<int, int, int>> toProcess;
    for (auto [y, c] : onPos[posMax])
      toProcess.emplace(y, posMax, c);

    int solFree = 0;
    int addL = 0, addR = 0;
    if (deb < posMax) {
      auto [toAdd, freeL] = dfs(dfs, deb, posMax, valMax);
      if (toAdd.size() > toProcess.size())
        toAdd.swap(toProcess);
      while (!toAdd.empty()) {
        toProcess.emplace(toAdd.top());
        toAdd.pop();
      }
      addL = freeL;
      solFree += freeL;
    }
    if (posMax + 1 < fin) {
      auto [toAdd, freeR] = dfs(dfs, posMax + 1, fin, valMax);
      if (toAdd.size() > toProcess.size())
        toAdd.swap(toProcess);
      while (!toAdd.empty()) {
        toProcess.emplace(toAdd.top());
        toAdd.pop();
      }
      addR = freeR;
      solFree += freeR;
    }
    fen.rangeAdd(posMax, fin, addL);
    fen.rangeAdd(deb, posMax + 1, addR);

    while (!toProcess.empty() and get<0>(toProcess.top()) <= prevHeight) {
      auto [y, x, c] = toProcess.top();
      toProcess.pop();
      int gain = c + fen.point(x);
      dbg(x, y, gain, fen.point(x));
      solFree = max(solFree, gain);
    }
    dbg(deb, fin, solFree);
    return pair(toProcess, solFree);
  };
  cout << totCost - DFS(DFS, 0, N, 1e18).second << endl;
}

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