Submission #1194757

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194757		LucaLucaM	Meetings (IOI18_meetings)	C++20	0 / 100	69 ms	9796 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;
    } else {
      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 Line {
  ll a, b;

  Line() : a(0), b(+INF) {}
  Line(ll a, ll b) : a(a), b(b) {}

  ll get(ll x) {
    return (ll) a * x + b;
  }

  void add(Line x) {
    a += x.a;
    b += x.b;
  }
};

struct Node {
  Line line = Line();
  Line lazy = Line(0, 0);

  Node *lc = nullptr;
  Node *rc = nullptr;

  void apply(ll l, ll r, Line v) {
    line.add(v);
    lazy.add(v);
  }
};

Node* root;
int sz;

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

void PushLazy(Node* &n, ll tl, ll tr) {
  if (n == nullptr) return;
  if (n->lc == nullptr) n->lc = new Node();
  if (n->rc == nullptr) n->rc = new Node();
  ll mid = (tl + tr) / 2;
  n->lc->apply(tl, mid, n->lazy);
  n->rc->apply(mid + 1, tr, n->lazy);
  n->lazy = Line(0, 0);
}

void minLineKnowingly(Node* &n, ll tl, ll tr, Line x) {
  if (n == nullptr) n = new Node();
  if (n->line.get(tl) > x.get(tl)) std::swap(n->line, x);
  if (n->line.get(tr) <= x.get(tr)) return;
  if (tl == tr) return;
  ll mid = (tl + tr) / 2;
  PushLazy(n, tl, tr);
  if (n->line.get(mid) < x.get(mid)) {
    minLineKnowingly(n->rc, mid + 1, tr, x);
  } else {
    std::swap(n->line, x);
    minLineKnowingly(n->lc, tl, mid, x);
  }
}
void PushLine(Node* &n, ll tl, ll tr) {
  if (n == nullptr) return;
  ll mid = (tl + tr) / 2;
  minLineKnowingly(n->lc, tl, mid, n->line);
  minLineKnowingly(n->rc, mid + 1, tr, n->line);
  n->line = Line();
}


void minLine(Node* &n, ll tl, ll tr, ll l, ll r, Line x) {
  if (tr < l || r < tl || tl > tr || l > r) return;
  if (n == nullptr) n = new Node();
  if (l <= tl && tr <= r) return minLineKnowingly(n, tl, tr, x);
  ll mid = (tl + tr) / 2;
  PushLazy(n, tl, tr);
  minLine(n->lc, tl, mid, l, r, x);
  minLine(n->rc, mid + 1, tr, l, r, x);
}

void addLine(Node* &n, ll tl, ll tr, ll l, ll r, Line x) {
  if (tr < l || r < tl || tl > tr || l > r) return;
  if (n == nullptr) n = new Node();
  if (l <= tl && tr <= r) return n->apply(tl, tr, x);
  ll mid = (tl + tr) / 2;
  PushLazy(n, tl, tr);
  PushLine(n, tl, tr);
  addLine(n->lc, tl, mid, l, r, x);
  addLine(n->rc, mid + 1, tr, l, r, x);
}

ll pointQuery(Node* &n, ll tl, ll tr, ll x) {
  if (n == nullptr) return +INF;
  if (tl == tr) return n->line.get(x);
  PushLazy(n, tl, tr);
  ll res = n->line.get(x);
  ll mid = (tl + tr) / 2;
  if (x <= mid) {
    res = std::min(res, pointQuery(n->lc, tl, mid, x));
  } else {
    res = std::min(res, pointQuery(n->rc, mid + 1, tr, x));
  }
  return res;
}

void minLine(int l, int r, Line x) {
  return minLine(root, 0, sz - 1, l, r, x);
}
void minLine(int l, int r, ll x, ll y) {
  minLine(l, r, Line(x, y));
}
void addLine(int l, int r, Line x) {
  return addLine(root, 0, sz - 1, l, r, x);
}
void addConstant(int l, int r, ll c) {
  addLine(l, r, Line(0, c));
}

ll pointQuery(int x) {
  return pointQuery(root, 0, sz - 1, x);
}
void pointUpdate(int p, ll x) {
  addConstant(p, p, x - 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);
  
  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], 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], 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 : 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));
    // }
    pointUpdate(p, c + a[p]);
    // // pref[p+1..r] 
    addConstant(p + 1, r, (ll) a[p] * (p - l + 1));
    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 = [&]() {
    init(n);
    for (int i = 0; i < n; i++) {
      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: 0 / 4
• Subtask 2: 0 / 15
• Subtask 3: 0 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40