Submission #1244928

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244928		2288	Meetings (IOI18_meetings)	C++20	19 / 100	5594 ms	22144 KiB

meetings

#include "meetings.h"
using namespace std;

#define ALL(x) begin(x),end(x)
#define pb push_back
#define F first
#define S second
// #define int long long

typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
typedef vector<vb> vvb;

template<typename T>
T meq(T& a, T b){
  return a=max(a,b);
}


#define D 20

std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
                                     std::vector<int> R) {
  int Q = L.size();
  int n = H.size();
  std::vector<long long> C(Q);
  
  vi lg(n+1);
  lg[0]=-10000000;lg[1]=0;
  for (int i=2;i<=n;i++)lg[i]=lg[i/2]+1;

  vvii mxs(D, vii(n)); // height, ind
  for (int i=0;i<n;i++)mxs[0][i]={H[i], i};
  for (int d=1;d<D;d++){
    for (int i=0;i<n;i++){
      mxs[d][i]=mxs[d-1][i];
      if(i+(1<<(d-1))<n)meq(mxs[d][i],mxs[d-1][i+(1<<(d-1))]);
    }
  }

  auto solve = [&](auto&& self, int l, int r) -> ll {
    int len = r-l;
    if (len==0)return 0;
    if (len==1)return H[l];
    int d = lg[len];
    auto [mx, pmx] = max(mxs[d][l], mxs[d][r-(1<<d)]);
    return min(
      ll(mx)*ll(pmx-l+1) + self(self, pmx+1, r),
      ll(mx)*ll(r-pmx) + self(self, l, pmx)
    );
  };

  for (int j = 0; j < Q; ++j) {
    C[j] = solve(solve, L[j], R[j]+1); 
  }
  return C;
}

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