제출 #999421

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
999421		MarwenElarbi	Meetings (IOI18_meetings)	C++17	19 / 100	5543 ms	6192 KiB

meetings

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
#define pb push_back
#define ii pair<int,int>
const int nax=2e5+5;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());


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);
  vector<long long> left(N);
  vector<long long> right(N);
  for (int j = 0; j < Q; ++j){
    C[j]=1e18;
    stack<int> st;
    left[L[j]]=H[L[j]];
    st.push(L[j]);
    for (int i = L[j]+1; i <= R[j]; ++i)
    {
      while(!st.empty()&&H[i]>=H[st.top()]) st.pop();
      if(st.size()) left[i]=left[st.top()]+1ll*(i-st.top())*H[i];
      else left[i]=1ll*(i-L[j]+1)*H[i];
      st.push(i);
    }
    /*for (int i = L[j]; i <= R[j]; ++i)
    {
      cout <<left[i]<<" ";
    }cout <<endl;*/
    while(!st.empty()) st.pop();
    right[R[j]]=H[R[j]];
    st.push(R[j]);
    for (int i = R[j]-1; i >= L[j]; --i)
    {
      while(!st.empty()&&H[i]>=H[st.top()]) st.pop();
      if(st.size()) right[i]=right[st.top()]+1ll*(st.top()-i)*H[i];
      else right[i]=1ll*(R[j]-i+1)*H[i];
      st.push(i);
    }
    /*for (int i = L[j]; i <= R[j]; ++i)
    {
      cout <<right[i]<<" ";
    }cout <<endl;*/
    C[j]=min(left[R[j]],right[L[j]]);
    for (int i = L[j]+1; i <= R[j]; ++i)
    {
      C[j]=min(C[j],left[i-1]+right[i]);
    }
  }
  return C;
}

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