Submission #1195024

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195024		LucaLucaM	Meetings (IOI18_meetings)	C++20	60 / 100	5565 ms	320524 KiB

meetings

#include "meetings.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <set>

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

using ll = long long;

const ll INF = 1e18;

struct RMQ {
  int n;
  std::vector<int> a;
  std::vector<std::vector<int>> rmq;
  
  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();
    int lg2 = std::__lg(n);
    rmq = std::vector<std::vector<int>>(lg2 + 1, std::vector<int>(n, n));
    
    for (int i = 0; i < n; i++) {
      rmq[0][i] = i;
    }
    for (int j = 1; j <= lg2; 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) {
    int k = std::__lg(r - l + 1);
    return myMax(rmq[k][l], rmq[k][r - (1 << k) + 1]);
  }
};

struct Brut {
  std::vector<ll> a;
  Brut() {}
  void init(int n) {
    a = std::vector<ll>(n, 0);
  }
  void addConstant(int l, int r, ll c) {
    for (int i = l; i <= r; i++) {
      a[i] += c;
    }
  }
  void minLine(int l, int r, int x, ll y)  {
    for (int i = l; i <= r; i++) {
      a[i] = std::min(a[i], (ll) x * i + y);
    }
  }
  void pointUpdate(int p, ll v) {
    a[p] = v;
  }
  ll pointQuery(int p) {
    return a[p];
  }
};

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;
    Line lazy;
    Node* l;
    Node* r;
    Node() {
      L = {0, +INF};
      lazy = {0, 0};
      l = r = nullptr;
    }
  };

  LiChao() {}

  int n;
  Node* root;

  void init(int _n) {
    n = _n;
    root = new Node();
  }

  void pushLazy(Node* &node, int tl, int tr) {
    if (tl != tr) {
      if (node -> l == nullptr) {
        node -> l = new Node();
      }
      if (node -> r == nullptr) {
        node -> r = new Node();
      }
      node -> l -> lazy = node -> l -> lazy + node -> lazy;
      node -> r -> lazy = node -> r -> lazy + node -> lazy;
    }

    node -> L = node -> L + node -> lazy;
    node -> lazy = {0, 0};
  }
  void insertLine(Node* &node, int tl, int tr, Line L) {
    if (node == nullptr) {
      node = new Node();
    }

    pushLazy(node, tl, tr);
    int mid = (tl + tr) / 2;
    bool lef = L.eval(tl) < node -> L.eval(tl);
    bool mi = L.eval(mid) < node -> L.eval(mid);
    if (mi) {
      std::swap(node -> L, L);
    }
    if (tl == tr) {
      return;
    }
    if (lef != mi) {
      insertLine(node -> l, tl, mid, L);
    } else {
      insertLine(node -> r, mid + 1, tr, L);
    }
  }
  void pushLine(Node* &node, int tl, int tr) {
    if (tl < tr) {
      int mid = (tl + tr) / 2;
      insertLine(node -> l, tl, mid, node -> L);
      insertLine(node -> r, mid + 1, tr, node -> L);
    } 
    
    node -> L = {0, +INF};
  }

  void addConstant(Node* &node, int tl, int tr, int l, int r, ll c) {
    if (node == nullptr) {
      node = new Node();
    }
    if (l <= tl && tr <= r) {
      node -> lazy.b += c;
    } else {
      pushLazy(node, tl, tr);
      pushLine(node, tl, tr);
      int mid = (tl + tr) / 2;
      if (l <= mid) {
        addConstant(node -> l, tl, mid, l, r, c);
      }
      if (mid < r) {
        addConstant(node -> r, mid + 1, tr, l, r, c);
      }
    }
  }

  void minLine(Node* &node, int tl, int tr, int l, int r, Line L) {
    if (node == nullptr) {
      node = new Node();
    }

    pushLazy(node, tl, tr);

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

  ll pointQuery(Node* &node, int tl, int tr, int p) {
    if (node == nullptr) {
      return +INF;
    }
    pushLazy(node, tl, tr);
    if (tl == tr) {
      return node -> L.eval(p);
    } 
    int mid = (tl + tr) / 2;
    if (p <= mid) {
      return std::min(node -> L.eval(p), pointQuery(node -> l, tl, mid, p));
    } else {
      return std::min(node -> L.eval(p), pointQuery(node -> r, mid + 1, tr, p));
    }
  }

  void addConstant(int l, int r, ll c) {
    if (l > r) {
      return;
    }
    assert(0 <= l && l <= r && r <= n - 1);
    addConstant(root, 0, n - 1, l, r, c);
  }
  void minLine(int l, int r, ll x, ll y) {
    if (l > r) {
      return;
    }
    assert(0 <= l && l <= r && r <= n - 1);
    minLine(root, 0, n - 1, l, r, Line(x, y));
  }
  ll pointQuery(int p) {
    return pointQuery(root, 0, n - 1, p);
  }
  void pointUpdate(int p, ll v) {
    addConstant(p, p, v - pointQuery(p));
  }
  void deb(Node* node, int tl, int tr) {
    if (node == nullptr) {
      return;
    }
    pushLazy(node, tl, tr);
    std::cout << " ? " << tl << ' ' << tr << '\n';
    assert(node -> lazy.a == 0);
    std::cout << node -> L.a << ' ' << node -> L.b << ' ' << node -> lazy.a << ' ' << node -> lazy.b << '\n';
    int mid = (tl + tr) / 2;
    deb(node -> l, tl, mid);
    deb(node -> r, mid + 1, tr);
  }
  void deb() {
    deb(root, 0, n - 1);
  }
};

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::set<std::pair<int, int>>> lHere(n);
  std::vector<std::set<std::pair<int, int>>> rHere(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
    if (p - l < r - p) {
      for (int st = l; st <= p; st++) {
        // iau mereu l cel mai mare
        while (!lHere[st].empty() && (*lHere[st].rbegin()).first >= p) {
          auto [dr, index] = *lHere[st].lower_bound({p, 0});
          if (dr <= r) {
            answer[index] = std::min(answer[index], DS.pointQuery(dr) + (ll) a[p] * (p - st + 1));
            lHere[st].erase({dr, index});
            rHere[dr].erase({st, index});
          } else {
            break;
          }
        }
      }
    } else {
      for (int dr = p; dr <= r; dr++) {
        while (!rHere[dr].empty() && (*rHere[dr].rbegin()).first >= l) {
          // vreau l minim
          auto [st, index] = *rHere[dr].lower_bound({l, 0});
          if (st <= p) {
            answer[index] = std::min(answer[index], DS.pointQuery(dr) + (ll) a[p] * (p - st + 1));
            lHere[st].erase({dr, index});
            rHere[dr].erase({st, index});
          } else {
            break;
          }
        } 
      }
    }

    // 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);
    // if (l == 2 && r == 2) {
    //   std::cout << debug(DS.pointQuery(2));
    //   std::cout << debug(c);
    //   DS.pointUpdate(p, c);
    //   std::cout << debug(DS.pointQuery(2));
    // }
    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++) {
      lHere[i].clear();
      rHere[i].clear();
    }
    for (int i = 0; i < q; i++) {
      lHere[L[i]].insert({R[i], i});
      rHere[R[i]].insert({L[i], i});
    }
  };

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

  // DS.init(n);
  // DS.deb();
  // std::cout << "\n\n";
  // DS.pointUpdate(0, 0);
  // std::cout << debug(DS.pointQuery(0));
  // DS.deb();
  // // DS.pointUpdate(1, 0);
  // // DS.pointUpdate(2, 0);
  // DS.pointUpdate(0, 1);
  // DS.deb();
  // std::cout << debug(DS.pointQuery(0));
  // // std::cout << DS.pointQuery(0) << '\n';
  // // DS.addConstant(0, 0, 1);
  // // std::cout << DS.pointQuery(0) << '\n';
  // answer[0] = -1;
  // return answer;
  
  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: 0 / 40