제출 #75486

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
75486		C_SUNSHINE	모임들 (IOI18_meetings)	C++14	19 / 100	5587 ms	4868 KiB

meetings

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <vector>
#include "meetings.h"
using namespace std;

typedef long long LL;

LL vl[750005],vr[750005];

std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L, std::vector<int> R)
{
  vector<LL> C;
  int Q=L.size();
  for(int qi=0;qi<Q;qi++)
  {
    int l=L[qi],r=R[qi];
    vector<int> st;
    st.clear();
    LL now=0;
    for(int i=l;i<=r;i++)
    {
      while(!st.empty()&&H[i]>H[st.back()])
      {
        if(st.size()==1)now-=((LL)st[0]-l+1)*H[st[0]];
        else now-=((LL)st[st.size()-1]-st[st.size()-2])*H[st.back()];
        st.pop_back();
      }
      if(st.size()==0)now+=((LL)i-l+1)*H[i];
      else now+=((LL)i-st.back())*H[i];
      st.push_back(i);
      vl[i]=now;
    }
    st.clear();
    now=0;
    for(int i=r;i>=l;i--)
    {
      while(!st.empty()&&H[i]>H[st.back()])
      {
        if(st.size()==1)now-=((LL)r-st[0]+1)*H[st[0]];
        else now-=((LL)st[st.size()-2]-st[st.size()-1])*H[st.back()];
        st.pop_back();
      }
      if(st.size()==0)now+=((LL)r-i+1)*H[i];
      else now+=((LL)st.back()-i)*H[i];
      st.push_back(i);
      vr[i]=now;
    }
    LL ans=1LL<<60;
    for(int i=l;i<=r;i++)
    {
      ans=min(ans,vl[i]+vr[i]-H[i]);
      //cout<<i<<' '<<vl[i]<<' '<<vr[i]<<endl;
    }
    C.push_back(ans);
  }
  return C;
}

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