Submission #1244942

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244942		2288	Meetings (IOI18_meetings)	C++20	0 / 100	0 ms	324 KiB

meetings

#include "meetings.h"
#include <numeric>
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 left(n),right(n);
  iota(ALL(left),0);
  iota(ALL(right),0);
  for (int i=0;i<n-1;i++)if(H[i]==1&&H[i+1]==1)left[i+1]=left[i];
  for (int i=n-1;i>0;i--)if(H[i]==1&&H[i-1]==1)right[i-1]=right[i];
  
  vi lg(n+1);
  lg[0]=-10000000;lg[1]=0;
  for (int i=2;i<=n;i++)lg[i]=lg[i/2]+1;

  vvi mxs(D, vi(n)); // height, ind
  for (int i=0;i<n;i++)mxs[0][i]=(H[i]==1)?right[i]-left[i]+1:0;
  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 = [&](int l, int r) -> ll {
    int len = r-l+1;
    int l2 = l, r2 = r, ans = 2*len;
    if (right[l]==right[r])return len;
    if (H[l]==1){
      l2 = right[l]+1;
      ans=min(ans,2*len+l-right[l]-1);
    }
    if (H[r]==1){
      r2 = left[r];
      ans=min(ans,2*len-r+left[r]-1);
    }
    int len2 = r2-l2;
    if (len2){
      int d = lg[len2];
      ans = min(ans, 2*len-max(mxs[d][l2], mxs[d][r2-(1<<d)]));
    }
    return ans;
  };

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

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