Submission #222839

#	Time	Username	Problem	Language	Result	Execution time	Memory
222839		rama_pang	Meetings (IOI18_meetings)	C++14	100 / 100	3625 ms	409828 KiB

meetings

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

using lint = long long;
const lint INF = 1e18;

class LiChao { // Li Chao Segment Tree
 private:
  struct Line { // y = ax + b
    lint a, b;
    lint get(lint x) { return a * x + b; }
    Line() {}
    Line(lint a, lint b) : a(a), b(b) {}
  };

  int sz;
  vector<Line> tree;
  vector<lint> lazy;

  void Apply(int n, lint x) {
    tree[n].b += x;
    lazy[n] += x;
  }

  void Push(int n, int lc, int rc) {
    Apply(lc, lazy[n]);
    Apply(rc, lazy[n]);
    lazy[n] = 0;
  }

  void SetLine(int n, int tl, int tr, int l, int r, Line line) {
    if (tr < l || r < tl || tl > tr || l > r) return;
    int mid = (tl + tr) / 2;
    int lc = n + 1;
    int rc = n + 2 * (mid - tl + 1);
    if (tl != tr) Push(n, lc, rc);
    if (l <= tl && tr <= r) {
      if (tree[n].get(tl) > line.get(tl)) swap(tree[n], line);
      if (tree[n].get(tr) <= line.get(tr)) return;
      if (tree[n].get(mid) <= line.get(mid)) {
        return SetLine(rc, mid + 1, tr, l, r, line);
      } else {
        swap(tree[n], line);
        return SetLine(lc, tl, mid, l, r, line);
      }
    }
    SetLine(lc, tl, mid, l, r, line);
    SetLine(rc, mid + 1, tr, l, r, line);
  }

  void RangeSumUpdate(int n, int tl, int tr, int l, int r, lint x) {
    if (tr < l || r < tl || tl > tr || l > r) return;
    if (l <= tl && tr <= r) return Apply(n, x);
    int mid = (tl + tr) / 2;
    int lc = n + 1;
    int rc = n + 2 * (mid - tl + 1);
    Push(n, lc, rc);
    RangeSumUpdate(lc, tl, mid, l, r, x);
    RangeSumUpdate(rc, mid + 1, tr, l, r, x);
  }

  lint Query(int n, int tl, int tr, int x) {
    lint res = tree[n].get(x);
    if (tl == tr) return res;
    int mid = (tl + tr) / 2;
    int lc = n + 1;
    int rc = n + 2 * (mid - tl + 1);
    Push(n, lc, rc);
    if (x <= mid) res = min(res, Query(lc, tl, mid, x));
    if (x > mid) res = min(res, Query(rc, mid + 1, tr, x));
    return res;
  }

 public:
  LiChao() {}
  LiChao(int n) : sz(n) {
    tree.assign(2 * sz, Line(0, INF));
    lazy.assign(2 * sz, 0);
  }

  void SetLine(int l, int r, lint a, lint b) {
    return SetLine(1, 0, sz - 1, l, r, Line(a, b));
  }

  void RangeSumUpdate(int l, int r, lint x) {
    return RangeSumUpdate(1, 0, sz - 1, l, r, x);
  }

  lint Query(int x) {
    return Query(1, 0, sz - 1, x);
  }
};

class SegmentTree {
 private:
  int sz;
  vector<pair<int, int>> tree;

 public:
  SegmentTree() {}
  SegmentTree(int n, vector<int> A) : sz(n) {
    tree.resize(2 * sz);
    for (int i = 0; i < sz; i++) {
      tree[i + sz] = {A[i], i};
    }
    for (int i = sz - 1; i >= 0; i--) {
      tree[i] = max(tree[i * 2], tree[i * 2 + 1]);
    }
  }

  int Query(int l, int r) {
    pair<int, int> res = {0, -1};
    for (l += sz, r += sz + 1; l < r; l /= 2, r /= 2) {
      if (l & 1) res = max(res, tree[l++]);
      if (r & 1) res = max(res, tree[--r]);
    }
    return res.second;
  }
};

struct query_t {
  int id;
  int l, r;
  query_t() {}
  query_t(int id, int ql, int qr) : id(id), l(ql), r(qr) {}
};

LiChao Left, Right;
SegmentTree RMQ;  

void Solve(int L, int R, const vector<int> &H, 
           const vector<vector<query_t>> &Query, vector<lint> &Answer) {
  if (L > R) return;
  int M = RMQ.Query(L, R);
  Solve(L, M - 1, H, Query, Answer);
  Solve(M + 1, R, H, Query, Answer);

  Left.SetLine(M, M, 0, 0);
  Right.SetLine(M, M, 0, 0);
  
  for (auto q : Query[M]) {
    Answer[q.id] = min(Left.Query(q.l) + 1ll * (q.r - M + 1) * H[M], 
                       Right.Query(q.r) + 1ll * (M - q.l + 1) * H[M]);
  }

  Left.RangeSumUpdate(L, M, 1ll * (R - M + 1) * H[M]);
  Left.SetLine(L, M, -H[M], 1ll * M * H[M]  + H[M] + (M < R ? Left.Query(M + 1) : 0));

  Right.RangeSumUpdate(M, R, 1ll * (M - L + 1) * H[M]);
  Right.SetLine(M, R, H[M], -1ll * M * H[M] + H[M] + (M > L ? Right.Query(M - 1) : 0));
}

vector<lint> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
  int N = H.size(), Q = L.size();

  RMQ = SegmentTree(N, H);
  Left = Right = LiChao(N);

  vector<vector<query_t>> Query(N);
  vector<lint> Answer(Q);

  for (int i = 0; i < Q; i++) {
    Query[RMQ.Query(L[i], R[i])].emplace_back(i, L[i], R[i]);
  }

  Solve(0, N - 1, H, Query, Answer);
  return Answer;
}

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