Submission #1005534

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005534		MilosMilutinovic	Meetings (IOI18_meetings)	C++14	100 / 100	1981 ms	478288 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>

using namespace std;

const int MAX = 750750;
const int NODES = 8 * MAX;
const int LOG = 20;
const long long inf = (long long) 1e18;

int n, q, a[MAX], ql[MAX], qr[MAX];
int logs[MAX], idx[MAX][LOG];
vector<int> qs[MAX];
vector<long long> res;

struct Line { 
  long long k;
  long long n;
  Line(long long _k = 0, long long _n = inf) : k(_k), n(_n) {}
  long long val(long long x) {
    return k * x + n;
  }
} seg[2][NODES];

long long tag[2][NODES];

int cmp(int i, int j) { return a[i] > a[j] ? i : j; }

int getMax(int l, int r) {
  int k = logs[r - l + 1];
  return cmp(idx[l][k], idx[r - (1 << k) + 1][k]);
}

void push(int t, int id) {
  seg[t][id * 2].n += tag[t][id];
  seg[t][id * 2 + 1].n += tag[t][id];
  tag[t][id * 2] += tag[t][id];
  tag[t][id * 2 + 1] += tag[t][id];
  tag[t][id] = 0;
}

void build(int id, int l, int r) {
  if (l == r) {
    seg[0][id] = Line(0, 0);
    seg[1][id] = Line(0, 0);
    return;
  }
  int mid = (l + r) >> 1;
  build(id * 2, l, mid);
  build(id * 2 + 1, mid + 1, r);
}

long long query(int t, int id, int l, int r, int p) {
  push(t, id);
  if (l == r) {
    return seg[t][id].val(p);
  }
  int mid = (l + r) >> 1;
  if (p <= mid) {
    return min(seg[t][id].val(p), query(t, id * 2, l, mid, p));
  } else {
    return min(seg[t][id].val(p), query(t, id * 2 + 1, mid + 1, r, p));
  }
}

void increase(int t, int id, int l, int r, int ll, int rr, long long v) {
  if (ll <= l && r <= rr) {
    seg[t][id].n += v;
    tag[t][id] += v;
    push(t, id);
    return;
  }
  push(t, id);
  int mid = (l + r) >> 1;
  if (rr <= mid) {
    increase(t, id * 2, l, mid, ll, rr, v);
  } else if (ll > mid) {
    increase(t, id * 2 + 1, mid + 1, r, ll, rr, v);
  } else {
    increase(t, id * 2, l, mid, ll, rr, v);
    increase(t, id * 2 + 1, mid + 1, r, ll, rr, v);
  }
}

void modify(int t, int id, int l, int r, int ll, int rr, Line ln) {
  if (l > r || l > rr || r < ll) {
    return;
  }
  push(t, id);
  int mid = (l + r) >> 1;
  if (ll <= l && r <= rr) {
    if (ln.val(mid) < seg[t][id].val(mid)) {
      swap(ln, seg[t][id]);
    }
    if (ln.val(l) < seg[t][id].val(l)) {
      modify(t, id * 2, l, mid, ll, rr, ln);
    } else {
      modify(t, id * 2 + 1, mid + 1, r, ll, rr, ln);
    }
    return;
  }
  modify(t, id * 2, l, mid, ll, rr, ln);
  modify(t, id * 2 + 1, mid + 1, r, ll, rr, ln);
}

void solve(int l, int r) {
  if (l > r) {
    return;
  }
  int mid = getMax(l, r);
  solve(l, mid - 1);
  solve(mid + 1, r);
  for (int i : qs[mid]) {
    res[i] = min(query(0, 1, 0, n - 1, qr[i]) + (mid - ql[i] + 1) * 1LL * a[mid],
              query(1, 1, 0, n - 1, ql[i]) + (qr[i] - mid + 1) * 1LL * a[mid]);
  }
  increase(0, 1, 0, n - 1, mid, r, a[mid] * 1LL * (mid - l + 1));
  increase(1, 1, 0, n - 1, l, mid, a[mid] * 1LL * (r - mid + 1));
  if (l != mid) {
    modify(0, 1, 0, n - 1, mid, r, Line(a[mid], query(0, 1, 0, n - 1, mid - 1) - (mid - 1) * 1LL * a[mid]));
  }
  if (r != mid) {
    modify(1, 1, 0, n - 1, l, mid, Line(-a[mid], query(1, 1, 0, n - 1, mid + 1) + (mid + 1) * 1LL * a[mid]));
  }
}

vector<long long> minimum_costs(vector<int> h, vector<int> l, vector<int> r) {
  n = (int) h.size();
  q = (int) l.size();
  for (int i = 0; i < n; i++) {
    a[i] = h[i];
  }
  for (int i = 0; i < q; i++) {
    ql[i] = l[i];
    qr[i] = r[i];
  }
  for (int i = 2; i <= n; i++) {
    logs[i] = logs[i >> 1] + 1;
  }
  for (int i = 0; i < n; i++) {
    idx[i][0] = i;
  }
  for (int j = 1; j < LOG; j++) {
    for (int i = 0; i + (1 << j) <= n; i++) {
      idx[i][j] = cmp(idx[i][j - 1], idx[i + (1 << (j - 1))][j - 1]);
    }
  }
  build(1, 0, n - 1);
  res.resize(q);
  for (int i = 0; i < q; i++) {
    qs[getMax(l[i], r[i])].push_back(i);
  }
  solve(0, n - 1);
  return res;
}

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