Submission #609120

#	Time	Username	Problem	Language	Result	Execution time	Memory
609120		piOOE	Meetings (IOI18_meetings)	C++17	100 / 100	2968 ms	495336 KiB

meetings

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

using namespace std;

using ll = long long;

const ll inf = 3e18;

struct segtree {
  segtree *left{}, *right{};
  ll lazy_k = -228, lazy_b = 0, first = 0, last = 0;
  //pushed line, value in first point, value in last point
  //if (k == -228) then this is just add b

  void apply(ll k, ll b, int l, int r) {
    if (k == -228) {
      lazy_b += b;
      first += b;
      last += b;
    } else {
      lazy_k = k, lazy_b = b;
      first = k * l + b;
      last = k * (r - 1) + b;
    }
  }

  void push(int l, int r) {
    if (!left) {
      left = new segtree(), right = new segtree();
    }
    int mid = (l + r) >> 1;
    left->apply(lazy_k, lazy_b, l, mid);
    right->apply(lazy_k, lazy_b, mid, r);
    lazy_k = -228, lazy_b = 0;
  }

  void pull() {
    first = left->first;
    last = right->last;
  }

  void update(int l, int r, ll a, ll k, ll b, int lx, int rx) {
    if (l >= rx || lx >= r) {
      return;
    } else if (l <= lx && rx <= r) {
      if (first + a <= k * lx + b) {
        apply(-228, a, lx, rx);
        return;
      } else if (last + a >= k * (rx - 1) + b) {
        apply(k, b, lx, rx);
        return;
      }
    }
    int mid = (lx + rx) >> 1;
    push(lx, rx);
    left->update(l, r, a, k, b, lx, mid);
    right->update(l, r, a, k, b, mid, rx);
    pull();
  }

  ll query(int i, int lx, int rx) {
    if (lx + 1 == rx) {
      return first;
    } else {
      push(lx, rx);
      int mid = (lx + rx) >> 1;
      if (i < mid) {
        return left->query(i, lx, mid);
      } else {
        return right->query(i, mid, rx);
      }
    }
  }
};

vector<ll> minimum_costs(vector<int> h, vector<int> L, vector<int> R) {
  int n = (int) h.size();
  int q = (int) L.size();
  vector<ll> ans(q, inf);
  for (int _ = 0; _ < 2; ++_) {

    int logn = __lg(n) + 1;
    vector<vector<pair<int, int>>> sp(logn);
    for (int l = 0; l < logn; ++l) {
      sp[l].resize(n - (1 << l) + 1);
      for (int i = 0; i <= n - (1 << l); ++i) {
        if (l == 0) {
          sp[l][i] = {h[i], -i};
        } else {
          sp[l][i] = max(sp[l - 1][i], sp[l - 1][i + (1 << (l - 1))]);
        }
      }
    }
    auto get_max = [&](int l, int r) {
      assert(r > l && l >= 0 && r <= n);
      int lg = __lg(r - l);
      return max(sp[lg][l], sp[lg][r - (1 << lg)]);
    };

    vector adj(n, array<int, 2>{-1, -1});
    vector<vector<array<int, 3>>> queries(n);

    vector<int> right(n), left(n);

    vector<int> stk;
    int root = -1;
    for (int i = 0; i < n; ++i) {
      while (!stk.empty() && h[stk.back()] < h[i]) {
        stk.pop_back();
      }
      if (!stk.empty()) {
        adj[i][0] = adj[stk.back()][1];
        adj[stk.back()][1] = i;
      } else {
        adj[i][0] = root;
        root = i;
      }
      stk.push_back(i);
    }

    for (int i = 0; i < q; ++i) {
      auto [hight, j] = get_max(L[i], R[i] + 1);
      j = -j;
      queries[j].push_back({L[i], R[i], i});
    }

    auto *t = new segtree();

    function<void(int)> dfs = [&](int v) {
      for (int to: adj[v]) {
        if (to != -1) {
          dfs(to);
        }
      }
      ll mx = h[v];
      for (auto [l, r, i]: queries[v]) {
        ans[i] = min(ans[i], (v - l + 1) * mx + (r == v ? 0 : t->query(r, 0, n)));
      }
      int l = adj[v][0] == -1 ? v : left[adj[v][0]];
      int r = adj[v][1] == -1 ? v : right[adj[v][1]];
      left[v] = l, right[v] = r;
      t->update(v, r + 1, mx * (v - l + 1), h[v], (l == v ? 0 : t->query(v - 1, 0, n)) - mx * (v - 1), 0, n);
    };

    dfs(root);

    reverse(h.begin(), h.end());
    for (int i = 0; i < q; ++i) {
      L[i] = n - L[i] - 1;
      R[i] = n - R[i] - 1;
      swap(L[i], R[i]);
    }
  }
  return ans;
}

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