제출 #1181265

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1181265		rxlfd314	모임들 (IOI18_meetings)	C++17	100 / 100	2631 ms	541864 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
template <class T> using vt = vector<T>;
#define size(x) (int((x).size()))
#define all(x) begin(x), end(x)
#define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)

struct Line {
  ll m, c;
  ll eval(const int x) {
    return m * x + c;
  }
};

struct Lichao {
  vt<Line> st;
  vt<ll> lz;
  Lichao(const int n) : st(n << 2, Line{0, (ll)1e18}), lz(n << 2) {}
  #define lc i << 1
  #define rc lc | 1
  void push(const int i) {
    if (!lz[i])
      return;
    st[lc].c += lz[i];
    lz[lc] += lz[i];
    st[rc].c += lz[i];
    lz[rc] += lz[i];
    lz[i] = 0;
  }
  void update(const int ql, const int qr, Line line, const int i, const int tl, const int tr) {
    if (tl > qr || tr < ql)
      return;
    const int tm = tl + tr >> 1;
    if (ql <= tl && tr <= qr) {
      if (line.eval(tm) < st[i].eval(tm))
        swap(line, st[i]);
      if (tl == tr)
        return;
      push(i);
      if (line.eval(tl) < st[i].eval(tl))
        update(ql, qr, line, lc, tl, tm);
      if (line.eval(tr) < st[i].eval(tr))
        update(ql, qr, line, rc, tm + 1, tr);
    } else {
      push(i);
      update(ql, qr, line, lc, tl, tm);
      update(ql, qr, line, rc, tm + 1, tr);
    }
  }
  void update(const int ql, const int qr, const Line line) {
    update(ql, qr, line, 1, 0, (size(st) >> 2) - 1);
  }
  void range_add(const int ql, const int qr, const ll v, const int i, const int tl, const int tr) {
    if (tl > qr || tr < ql)
      return;
    if (ql <= tl && tr <= qr)
      st[i].c += v, lz[i] += v;
    else {
      push(i);
      const int tm = tl + tr >> 1;
      range_add(ql, qr, v, lc, tl, tm);
      range_add(ql, qr, v, rc, tm + 1, tr);
    }
  }
  void range_add(const int ql, const int qr, const ll v) {
    range_add(ql, qr, v, 1, 0, (size(st) >> 2) - 1);
  }
  ll query(const int x, const int i, const int tl, const int tr) {
    if (tl == tr)
      return st[i].eval(x);
    push(i);
    const int tm = tl + tr >> 1;
    if (x <= tm)
      return min(st[i].eval(x), query(x, lc, tl, tm));
    return min(st[i].eval(x), query(x, rc, tm + 1, tr));
  }
  ll query(const int x) {
    return query(x, 1, 0, (size(st) >> 2) - 1);
  }
  #undef lc
  #undef rc
};

struct ST {
  vt<vt<ari2>> st;
  ST(const vt<int> &A) {
    const int N = size(A), LOG = 31 - __builtin_clz(N);
    st.resize(N, vt<ari2>(LOG + 1));
    FOR(i, 0, N-1)
      st[i][0] = {A[i], i};
    FOR(j, 1, LOG)
      FOR(i, 0, N-(1<<j))
        st[i][j] = max(st[i][j-1], st[i+(1<<j-1)][j-1]);
  }
  int query(const int l, const int r) {
    const int n = 31 - __builtin_clz(r - l + 1);
    return max(st[l][n], st[r-(1<<n)+1][n])[1];
  }
};

vt<ll> minimum_costs(vt<int> A, vt<int> L, vt<int> R) {
  const int N = size(A);
  const int Q = size(L);
  ST st(A);
  vt<vt<int>> queries(N);
  FOR(i, 0, Q-1)
    queries[st.query(L[i], R[i])].push_back(i);
  vt<ll> ans(Q);
  Lichao lct_left(N), lct_right(N);
  auto solve = [&](auto &&self, const int l, const int r) -> void {
    if (l > r)
      return;
    
    const int m = st.query(l, r);
    self(self, l, m - 1);
    self(self, m + 1, r);
    
    lct_left.update(m, m, {0, 0});
    lct_right.update(m, m, {0, 0});
    
    for (const auto &qi : queries[m]) {
      const ll lv = lct_left.query(L[qi]) + 1ll * (R[qi] - m + 1) * A[m];
      const ll rv = lct_right.query(R[qi]) + 1ll * (m - L[qi] + 1) * A[m];
      ans[qi] = min(lv, rv);
    }
    
    lct_left.range_add(l, m, 1ll * A[m] * (r - m + 1));
    lct_left.update(l, m, {-A[m], lct_left.query(m+1) + 1ll * A[m] * (1 + m)});
    
    lct_right.range_add(m, r, 1ll * A[m] * (m - l + 1));
    lct_right.update(m, r, {A[m], lct_right.query(m-1) + 1ll * A[m] * (1 - m)});
  };
  solve(solve, 0, N - 1);
  return ans;
}

• Subtask 1: 4 / 4
• Subtask 2: 15 / 15
• Subtask 3: 17 / 17
• Subtask 4: 24 / 24
• Subtask 5: 40 / 40