Submission #684875

#	Time	Username	Problem	Language	Result	Execution time	Memory
684875		peijar	Constellation 3 (JOI20_constellation3)	C++17	100 / 100	183 ms	124732 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

inline char gc() { // like getchar()
  static char buf[1 << 16];
  static size_t bc, be;
  if (bc >= be) {
    buf[0] = 0, bc = 0;
    be = fread(buf, 1, sizeof(buf), stdin);
  }
  return buf[bc++]; // returns 0 on EOF
}

int readInt() {
  int a, c;
  while ((a = gc()) < 40)
    ;
  if (a == '-')
    return -readInt();
  while ((c = gc()) >= 48)
    a = a * 10 + c - 480;
  return a - 48;
}

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>>;

vector<vector<pair<int, int>>> onPos;
RMQ<pair<int, int>> rmq({});
Fenwick<int> fen(0);

pair<min_pq<tuple<int, int, int>>, int> dfs(int deb, int fin, int prevHeight) {
  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(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(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(move(toProcess), solFree);
}

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

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

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

  cout << totCost - dfs(0, N, 1e18).second << endl;
}

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