oj.uz

답안 #778839

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
778839 2023-07-10T20:03:36 Z qthang2k11 모임들 (IOI18_meetings) C++14
100 / 100
 2216 ms 310936 KB 
#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);
    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, bool le, bool ri) {
  if (L > R) return;
  int M = RMQ.Query(L, R);
  Solve(L, M - 1, H, Query, Answer, true, true);
  Solve(M + 1, R, H, Query, Answer, true, true);
 
  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]);
  }
 
  if (le) {
    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));
  }
 
  if (ri) {
    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, true, true);
  return Answer;
}

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 3 ms 724 KB Output is correct
3 Correct 4 ms 724 KB Output is correct
4 Correct 3 ms 724 KB Output is correct
5 Correct 3 ms 724 KB Output is correct
6 Correct 3 ms 980 KB Output is correct
7 Correct 3 ms 724 KB Output is correct
8 Correct 3 ms 1108 KB Output is correct
9 Correct 3 ms 852 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 3 ms 724 KB Output is correct
3 Correct 4 ms 724 KB Output is correct
4 Correct 3 ms 724 KB Output is correct
5 Correct 3 ms 724 KB Output is correct
6 Correct 3 ms 980 KB Output is correct
7 Correct 3 ms 724 KB Output is correct
8 Correct 3 ms 1108 KB Output is correct
9 Correct 3 ms 852 KB Output is correct
10 Correct 8 ms 1256 KB Output is correct
11 Correct 7 ms 1344 KB Output is correct
12 Correct 9 ms 1236 KB Output is correct
13 Correct 7 ms 1236 KB Output is correct
14 Correct 8 ms 1748 KB Output is correct
15 Correct 7 ms 1236 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 35 ms 4292 KB Output is correct
3 Correct 185 ms 28896 KB Output is correct
4 Correct 173 ms 18668 KB Output is correct
5 Correct 164 ms 32068 KB Output is correct
6 Correct 172 ms 33028 KB Output is correct
7 Correct 194 ms 35896 KB Output is correct

Subtask #4
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 35 ms 4292 KB Output is correct
3 Correct 185 ms 28896 KB Output is correct
4 Correct 173 ms 18668 KB Output is correct
5 Correct 164 ms 32068 KB Output is correct
6 Correct 172 ms 33028 KB Output is correct
7 Correct 194 ms 35896 KB Output is correct
8 Correct 176 ms 21580 KB Output is correct
9 Correct 162 ms 21656 KB Output is correct
10 Correct 163 ms 21596 KB Output is correct
11 Correct 179 ms 20512 KB Output is correct
12 Correct 160 ms 20516 KB Output is correct
13 Correct 160 ms 20804 KB Output is correct
14 Correct 178 ms 30964 KB Output is correct
15 Correct 168 ms 20548 KB Output is correct
16 Correct 193 ms 31148 KB Output is correct

Subtask #5
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 3 ms 724 KB Output is correct
3 Correct 4 ms 724 KB Output is correct
4 Correct 3 ms 724 KB Output is correct
5 Correct 3 ms 724 KB Output is correct
6 Correct 3 ms 980 KB Output is correct
7 Correct 3 ms 724 KB Output is correct
8 Correct 3 ms 1108 KB Output is correct
9 Correct 3 ms 852 KB Output is correct
10 Correct 8 ms 1256 KB Output is correct
11 Correct 7 ms 1344 KB Output is correct
12 Correct 9 ms 1236 KB Output is correct
13 Correct 7 ms 1236 KB Output is correct
14 Correct 8 ms 1748 KB Output is correct
15 Correct 7 ms 1236 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 35 ms 4292 KB Output is correct
18 Correct 185 ms 28896 KB Output is correct
19 Correct 173 ms 18668 KB Output is correct
20 Correct 164 ms 32068 KB Output is correct
21 Correct 172 ms 33028 KB Output is correct
22 Correct 194 ms 35896 KB Output is correct
23 Correct 176 ms 21580 KB Output is correct
24 Correct 162 ms 21656 KB Output is correct
25 Correct 163 ms 21596 KB Output is correct
26 Correct 179 ms 20512 KB Output is correct
27 Correct 160 ms 20516 KB Output is correct
28 Correct 160 ms 20804 KB Output is correct
29 Correct 178 ms 30964 KB Output is correct
30 Correct 168 ms 20548 KB Output is correct
31 Correct 193 ms 31148 KB Output is correct
32 Correct 1642 ms 153304 KB Output is correct
33 Correct 1307 ms 157588 KB Output is correct
34 Correct 1360 ms 157512 KB Output is correct
35 Correct 1622 ms 155280 KB Output is correct
36 Correct 1393 ms 156144 KB Output is correct
37 Correct 1395 ms 158168 KB Output is correct
38 Correct 1841 ms 233908 KB Output is correct
39 Correct 1894 ms 233884 KB Output is correct
40 Correct 1664 ms 165316 KB Output is correct
41 Correct 1988 ms 310656 KB Output is correct
42 Correct 2210 ms 310936 KB Output is correct
43 Correct 2216 ms 310924 KB Output is correct
44 Correct 2045 ms 233668 KB Output is correct