Submission #1194645

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194645		LucaLucaM	Meetings (IOI18_meetings)	C++20	19 / 100	5596 ms	35120 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) {
    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 p = l;
    for (int i = l; i <= r; i++) {
      p = myMax(p, i);
    }
    return p;
    int k = std::__lg(r - l + 1);
    return myMax(rmq[k][l], rmq[k][r - (1 << k) + 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);
  std::vector<ll> pref(n);

  std::vector<std::set<std::pair<int, int>>> lHere(n);
  std::vector<std::set<std::pair<int, int>>> rHere(n);

  RMQ rmq;
  rmq.build(a);

  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], pref[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], pref[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 : pref[p - 1];
    pref[p] = c + a[p];
    // pref[p+1..r] 
    for (int i = p + 1; i <= r; i++) {
      pref[i] += (ll) a[p] * (p - l + 1);
    }
    for (int i = p + 1; i <= r; i++) {
      pref[i] = std::min(pref[i], c + (ll) a[p] * (i - 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});
    }
  };

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

  std::reverse(a.begin(), a.end());
  rmq.build(a);
  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]);
  }

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

  return answer;
}

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