Submission #1194630

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194630		LucaLucaM	Meetings (IOI18_meetings)	C++20	19 / 100	5596 ms	24568 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: 4 / 4
• Subtask 2: 15 / 15
• Subtask 3: 0 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40