Submission #1194631

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194631		LucaLucaM	Meetings (IOI18_meetings)	C++20	0 / 100	104 ms	7572 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;

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);

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

    int p = l;
    for (int i = l + 1; i <= r; i++) {
      if (a[i] > a[p]) {
        p = i;
      }
    }


    
    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 >= 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;
          }
        }
      }
    } 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;
          }
        } 
      }
    }
    // for (int i = 0; i < q; i++) {
    //   if (l <= L[i] && L[i] <= p && p <= R[i] && R[i] <= r) {
    //     answer[i] = std::min(answer[i], pref[R[i]] + (ll) a[p] * (p - L[i] + 1));
    //   }
    // }

    // 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());
  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: 0 / 4
• Subtask 2: 0 / 15
• Subtask 3: 0 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40