Submission #1195056

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195056		LucaLucaM	Meetings (IOI18_meetings)	C++20	100 / 100	3834 ms	462768 KiB

meetings

#include "meetings.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <set>
#pragma GCC optimize("O3")

#define debug(x) #x << " = " << x  << '\n'

using ll = long long;

const ll INF = 1e18;
const ll ALMOSTINF = 1e15;

struct RMQ {
  int n;
  std::vector<int> a;
  std::vector<std::vector<int>> rmq;
  std::vector<int> lg2;

  int myMax(int x, int y) {
    if (a[x] == a[y]) {
      return x < y? x : y;
    }
    return a[x] >= a[y]? x : y;
  }

  RMQ() {}
  void build(const std::vector<int> &_a)  {
    a = _a;
    n = (int) a.size();
    
    lg2.resize(n + 1);
    lg2[1] = 0;
    for (int i = 2; i <= n; i++) {
      lg2[i] = lg2[i >> 1] + 1;
    }

    int sz = std::__lg(n);
    rmq = std::vector<std::vector<int>>(sz + 1, std::vector<int>(n, n));
    
    for (int i = 0; i < n; i++) {
      rmq[0][i] = i;
    }
    for (int j = 1; j <= sz; j++) {
      for (int i = 0; i + (1 << j) - 1 < n; i++) {
        rmq[j][i] = myMax(rmq[j - 1][i], rmq[j - 1][i + (1 << (j - 1))]);
      }
    }
  }

  int query(int l, int r) {
    assert(1 <= r - l + 1 && r - l + 1 <= n);
    int k = lg2[r - l + 1];
    return myMax(rmq[k][l], rmq[k][r - (1 << k) + 1]);
  }
};

struct LiChao {
  struct Line {
    ll a, b;
    Line() {}
    Line(ll x, ll y) : a(x), b(y) {}
    Line operator + (const Line &other) const {
      return Line(a + other.a, b + other.b);
    }
    ll eval(ll x) {
      return (ll) a * x + b;
    }
  };

  struct Node {
    Line L;
    ll lazy;
    Node() {
      L = {0, +INF};
      lazy = 0;
    }
  };

  LiChao() {}

  int n;
  std::vector<Node> aint;

  void init(int _n) {
    n = _n;
    aint.resize(4 * n + 1);
    for (int i = 0; i < (int) aint.size(); i++) {
      aint[i] = Node();
    }
  }

  void pushLazy(int node, int tl, int tr) {
    if (tl != tr && aint[node].lazy != 0) {
      aint[2 * node].lazy = aint[2 * node].lazy + aint[node].lazy;
      aint[2 * node + 1].lazy = aint[2 * node + 1].lazy + aint[node].lazy;
    }

    aint[node].L.b = aint[node].L.b + aint[node].lazy;
    aint[node].lazy = 0;
  }

  void insertLine(int node, int tl, int tr, Line L) {
    if (L.b >= ALMOSTINF) {
      return;
    }
    pushLazy(node, tl, tr);
    int mid = (tl + tr) / 2;
    bool lef = L.eval(tl) < aint[node].L.eval(tl);
    bool mi = L.eval(mid) < aint[node].L.eval(mid);
    if (mi) {
      std::swap(aint[node].L, L);
    }
    if (tl == tr) {
      return;
    }
    if (lef != mi) {
      insertLine(2 * node, tl, mid, L);
    } else {
      insertLine(2 * node + 1, mid + 1, tr, L);
    }
  }
  void pushLine(int node, int tl, int tr) {
    if (tl < tr) {
      int mid = (tl + tr) / 2;
      insertLine(2 * node, tl, mid, aint[node].L);
      insertLine(2 * node + 1, mid + 1, tr, aint[node].L);
    } 
    
    aint[node].L = {0, +INF};
  }

  void addConstant(int node, int tl, int tr, int l, int r, ll c) {
    if (l <= tl && tr <= r) {
      aint[node].lazy += c;
    } else {
      pushLazy(node, tl, tr);
      pushLine(node, tl, tr);
      int mid = (tl + tr) / 2;
      if (l <= mid) {
        addConstant(2 * node, tl, mid, l, r, c);
      }
      if (mid < r) {
        addConstant(2 * node + 1, mid + 1, tr, l, r, c);
      }
    }
  }

  void minLine(int node, int tl, int tr, int l, int r, Line L) {
    pushLazy(node, tl, tr);

    if (l <= tl && tr <= r) {
      insertLine(node, tl, tr, L);  
    } else {
      int mid = (tl + tr) / 2;
      if (l <= mid) {
        minLine(2 * node, tl, mid, l, r, L);
      } 
      if (mid < r) {
        minLine(2 * node + 1, mid + 1, tr, l, r, L);
      }
    }
  }

  ll pointQuery(int node, int tl, int tr, int p) {
    pushLazy(node, tl, tr);
    if (tl == tr) {
      return aint[node].L.eval(p);
    } 
    int mid = (tl + tr) / 2;
    if (p <= mid) {
      return std::min(aint[node].L.eval(p), pointQuery(2 * node, tl, mid, p));
    } else {
      return std::min(aint[node].L.eval(p), pointQuery(2 * node + 1, mid + 1, tr, p));
    }
  }

  void addConstant(int l, int r, ll c) {
    if (l > r) {
      return;
    }
    addConstant(1, 0, n - 1, l, r, c);
  }
  void minLine(int l, int r, ll x, ll y) {
    if (l > r) {
      return;
    }
    minLine(1, 0, n - 1, l, r, Line(x, y));
  }
  ll pointQuery(int p) {
    return pointQuery(1, 0, n - 1, p);
  }
  void pointUpdate(int p, ll v) {
    addConstant(p, p, v - pointQuery(p));
  }
};

std::vector<ll> minimum_costs(std::vector<int> a, std::vector<int> L, std::vector<int> R) {
  int n = (int) a.size();
  int q = (int) L.size();

  std::vector<ll> answer(q, +INF);
  
  LiChao DS;
  RMQ rmq;

  std::vector<std::vector<int>> queries(n);

  auto solve = [&](auto &&self, int l, int r) -> void {
    if (l > r) {
      return;
    }

    int p = rmq.query(l, r);
    
    self(self, l, p - 1);
    self(self, p + 1, r);

    // raspund la query uri
    
    for (int index : queries[p]) {
      answer[index] = std::min(answer[index], DS.pointQuery(R[index]) + (ll) a[p] * (p - L[index] + 1));
    }

    // acum trebuie sa recalculez pref[l..r]
    // pref[l..p-1] ramane la fel
    // pref[p]
    ll c = p == l? 0 : DS.pointQuery(p - 1);
    DS.pointUpdate(p, c + a[p]);
    // // pref[p+1..r] 
    DS.addConstant(p + 1, r, (ll) a[p] * (p - l + 1));
    DS.minLine(p + 1, r, a[p], c + (ll) a[p] * (-p + 1));
  }; 

  auto addQueries = [&]() {
    for (int i = 0; i < n; i++) {
      queries[i].clear();
    }
    for (int i = 0; i < q; i++) {
      queries[rmq.query(L[i], R[i])].push_back(i);
    }
  };

  auto prepare = [&]() {
    DS.init(n);
    for (int i = 0; i < n; i++) {
      DS.pointUpdate(i, 0);
    }
    rmq.build(a);
    addQueries();
  };
  
  prepare();
  solve(solve, 0, n - 1);

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

  prepare();
  solve(solve, 0, n - 1);

  return answer;
}

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