oj.uz

Submission #778856

# Submission time Handle Problem Language Result Execution time Memory
778856 2023-07-10T21:05:32 Z qthang2k11 Meetings (IOI18_meetings) C++14
100 / 100
 2877 ms 335704 KB 
#ifndef LOCAL 
#include "meetings.h"
#endif
#include <bits/stdc++.h>
using namespace std;

#define left defined_left
#define right defined_right

using ll = long long;

const int N = 750005;

int n, q, a[N], x[N], y[N];
vector<ll> ans;

vector<int> qr[N];

int sp[23][N];

inline int get_pos(int x, int y) {
  return (a[x] > a[y] ? x : y);
}

inline int get_max(int l, int r) {
  int k = __lg(r - l + 1);
  return get_pos(sp[k][l], sp[k][r - (1 << k) + 1]);
}

static const ll INF = 1e18;
struct Line {
  ll a, b;
  Line() { a = 0; b = INF; }
  Line(ll a, ll b): a(a), b(b) {}
  inline ll operator() (ll x) const {
    return a * x + b;
  }
};

struct ExtendedLichaoTree { 
  // +(0, x) in range [x, y]
  // insert(a, b) in range [x, y]
  // query(x)
  // similar to (update range, get point)
  Line IT[N << 2];
  ll lazy[N << 2];
  ExtendedLichaoTree() = default;
  void push(int id) {
    ll &val = lazy[id];
    if (val == 0) return;
    IT[id << 1].b += val;
    lazy[id << 1] += val;
    IT[id << 1 | 1].b += val;
    lazy[id << 1 | 1] += val;
    val = 0;
  }
  void update(int x, int y, ll val, int id, int l, int r) {
    if (l > y || r < x) return;
    if (x <= l && r <= y) {
      IT[id].b += val;
      lazy[id] += val;
      return;
    }
    int mid = (l + r) / 2;
    update(x, y, val, id << 1, l, mid);
    update(x, y, val, id << 1 | 1, mid + 1, r);
  }
  inline void update(int x, int y, ll val) {
    // +(0, val) in range [x, y]
    if (x <= y) update(x, y, val, 1, 1, n);
  }
  void insert(int x, int y, Line val, int id, int l, int r) {
    if (l > y || r < x) return;
    int mid = (l + r) / 2;
    if (l != r) push(id); // must push before update current value
    if (x <= l && r <= y) {
      if (l == r) {
        if (IT[id](l) > val(l)) swap(IT[id], val);
        return;
      }
      if (IT[id].a > val.a) swap(IT[id], val);
      if (IT[id](mid) > val(mid)) {
        swap(IT[id], val);
        insert(x, y, val, id << 1 | 1, mid + 1, r);
      } else {
        insert(x, y, val, id << 1, l, mid);
      }
      return;
    }
    insert(x, y, val, id << 1, l, mid);
    insert(x, y, val, id << 1 | 1, mid + 1, r);
  }
  inline void insert(int x, int y, Line val) {
    // insert(a, b) in range [x, y]
    if (x <= y) insert(x, y, val, 1, 1, n);
  }
  ll query(int x, int id, int l, int r) {
    if (l == r) return IT[id](x);
    push(id);
    int mid = (l + r) / 2;
    if (x <= mid) return min(IT[id](x), query(x, id << 1, l, mid));
    else return min(IT[id](x), query(x, id << 1 | 1, mid + 1, r));
  }
  inline ll query(int x) {
    // query(x)
    return query(x, 1, 1, n);
  }
} left, right;

void solve(int l, int r) {
  if (l > r) return;
  int m = get_max(l, r);
  solve(l, m - 1);
  solve(m + 1, r);
  left.insert(m, m, Line(0, 0));
  right.insert(m, m, Line(0, 0));
  for (int id: qr[m]) {
    int x = ::x[id], y = ::y[id];
    ll res = left.query(x) + 1LL * (y - m + 1) * a[m];
    res = min(res, 1LL * (m - x + 1) * a[m] + right.query(y));
    ans[id] = res;
  }
  left.update(l, m, 1LL * (r - m + 1) * a[m]);
  left.insert(l, m, Line(-a[m], 1LL * a[m] * (m + 1) + (m < r ? left.query(m + 1) : 0)));
  right.update(m, r, 1LL * (m - l + 1) * a[m]);
  right.insert(m, r, Line(a[m], -1LL * a[m] * (m - 1) + (l < m ? right.query(m - 1) : 0)));
}

vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
  n = H.size();
  q = L.size();
  ans.assign(q, 0);
  for (int i = 1; i <= n; i++) {
    a[i] = H[i - 1];
    sp[0][i] = i;
  }
  for (int k = 1; (1 << k) <= n; k++) {
    for (int i = 1; i + (1 << k) - 1 <= n; i++) {
      sp[k][i] = get_pos(sp[k - 1][i], sp[k - 1][i + (1 << (k - 1))]);
    }
  }
  for (int i = 0; i < q; i++) {
    x[i] = L[i] + 1;
    y[i] = R[i] + 1;
    qr[get_max(x[i], y[i])].emplace_back(i);
  }
  solve(1, n);
  return ans;
}

#ifdef LOCAL
int32_t main() {
  cin.tie(0)->sync_with_stdio(0);
  int n, q;
  cin >> n >> q;
  vector<int> H(n);
  for (int &x: H) cin >> x;
  vector<int> L(q), R(q);
  for (int i = 0; i < q; i++) cin >> L[i] >> R[i];
  vector<ll> ans = minimum_costs(H, L, R);
  for (ll x: ans) cout << x << '\n';
  return 0;
}
#endif

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 111772 KB Output is correct
2 Correct 43 ms 112216 KB Output is correct
3 Correct 45 ms 112256 KB Output is correct
4 Correct 44 ms 112212 KB Output is correct
5 Correct 44 ms 112204 KB Output is correct
6 Correct 44 ms 112328 KB Output is correct
7 Correct 53 ms 112156 KB Output is correct
8 Correct 44 ms 112360 KB Output is correct
9 Correct 43 ms 112292 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 111772 KB Output is correct
2 Correct 43 ms 112216 KB Output is correct
3 Correct 45 ms 112256 KB Output is correct
4 Correct 44 ms 112212 KB Output is correct
5 Correct 44 ms 112204 KB Output is correct
6 Correct 44 ms 112328 KB Output is correct
7 Correct 53 ms 112156 KB Output is correct
8 Correct 44 ms 112360 KB Output is correct
9 Correct 43 ms 112292 KB Output is correct
10 Correct 48 ms 112808 KB Output is correct
11 Correct 48 ms 112808 KB Output is correct
12 Correct 49 ms 112804 KB Output is correct
13 Correct 51 ms 112728 KB Output is correct
14 Correct 49 ms 113004 KB Output is correct
15 Correct 47 ms 112804 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 111820 KB Output is correct
2 Correct 69 ms 115404 KB Output is correct
3 Correct 216 ms 133868 KB Output is correct
4 Correct 188 ms 128076 KB Output is correct
5 Correct 200 ms 135828 KB Output is correct
6 Correct 215 ms 136224 KB Output is correct
7 Correct 236 ms 136612 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 111820 KB Output is correct
2 Correct 69 ms 115404 KB Output is correct
3 Correct 216 ms 133868 KB Output is correct
4 Correct 188 ms 128076 KB Output is correct
5 Correct 200 ms 135828 KB Output is correct
6 Correct 215 ms 136224 KB Output is correct
7 Correct 236 ms 136612 KB Output is correct
8 Correct 187 ms 128512 KB Output is correct
9 Correct 179 ms 128492 KB Output is correct
10 Correct 178 ms 128584 KB Output is correct
11 Correct 187 ms 127908 KB Output is correct
12 Correct 171 ms 127904 KB Output is correct
13 Correct 175 ms 128076 KB Output is correct
14 Correct 210 ms 133528 KB Output is correct
15 Correct 185 ms 127864 KB Output is correct
16 Correct 235 ms 134260 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 111772 KB Output is correct
2 Correct 43 ms 112216 KB Output is correct
3 Correct 45 ms 112256 KB Output is correct
4 Correct 44 ms 112212 KB Output is correct
5 Correct 44 ms 112204 KB Output is correct
6 Correct 44 ms 112328 KB Output is correct
7 Correct 53 ms 112156 KB Output is correct
8 Correct 44 ms 112360 KB Output is correct
9 Correct 43 ms 112292 KB Output is correct
10 Correct 48 ms 112808 KB Output is correct
11 Correct 48 ms 112808 KB Output is correct
12 Correct 49 ms 112804 KB Output is correct
13 Correct 51 ms 112728 KB Output is correct
14 Correct 49 ms 113004 KB Output is correct
15 Correct 47 ms 112804 KB Output is correct
16 Correct 40 ms 111820 KB Output is correct
17 Correct 69 ms 115404 KB Output is correct
18 Correct 216 ms 133868 KB Output is correct
19 Correct 188 ms 128076 KB Output is correct
20 Correct 200 ms 135828 KB Output is correct
21 Correct 215 ms 136224 KB Output is correct
22 Correct 236 ms 136612 KB Output is correct
23 Correct 187 ms 128512 KB Output is correct
24 Correct 179 ms 128492 KB Output is correct
25 Correct 178 ms 128584 KB Output is correct
26 Correct 187 ms 127908 KB Output is correct
27 Correct 171 ms 127904 KB Output is correct
28 Correct 175 ms 128076 KB Output is correct
29 Correct 210 ms 133528 KB Output is correct
30 Correct 185 ms 127864 KB Output is correct
31 Correct 235 ms 134260 KB Output is correct
32 Correct 1452 ms 243932 KB Output is correct
33 Correct 1150 ms 243764 KB Output is correct
34 Correct 1248 ms 244032 KB Output is correct
35 Correct 1431 ms 245436 KB Output is correct
36 Correct 1130 ms 244388 KB Output is correct
37 Correct 1251 ms 244236 KB Output is correct
38 Correct 1884 ms 289144 KB Output is correct
39 Correct 1836 ms 289172 KB Output is correct
40 Correct 1518 ms 250236 KB Output is correct
41 Correct 2478 ms 332568 KB Output is correct
42 Correct 2877 ms 335696 KB Output is correct
43 Correct 2638 ms 335704 KB Output is correct
44 Correct 2240 ms 290768 KB Output is correct