Submission #778856

#	Time	Username	Problem	Language	Result	Execution time	Memory
778856		qthang2k11	Meetings (IOI18_meetings)	C++14	100 / 100	2877 ms	335704 KiB

meetings

#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 / 4
• Subtask 2: 15 / 15
• Subtask 3: 17 / 17
• Subtask 4: 24 / 24
• Subtask 5: 40 / 40