Submission #1032938

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032938		amirhoseinfar1385	Meetings (IOI18_meetings)	C++17	19 / 100	5547 ms	48708 KiB

meetings

#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
const long long maxn=750000+10;
long long all[maxn],n,dpl[maxn],dpr[maxn],tr[maxn],tl[maxn],psl[maxn],psr[maxn],inf=1e16;
vector<pair<long long,long long>>allql[maxn],allqr[maxn];
long long q,res[maxn];

void caltltr(){
  vector<long long>v;
  all[0]=inf;
  all[n+1]=inf;
  v.push_back(0);
  for(long long i=1;i<=n;i++){
    while(all[v.back()]<all[i]){
      v.pop_back();
    }
    tl[i]=v.back();
    v.push_back(i);
  }
  v.clear();
  v.push_back(n+1);
  for(long long i=n;i>=1;i--){
    while(all[v.back()]<all[i]){
      v.pop_back();
    }
    tr[i]=v.back();
    v.push_back(i);
  }
}

void solvel(){
  vector<long long>v;
    v.push_back(0);
  for(long long i=1;i<=n;i++){
    dpl[i]=inf;
    while(all[v.back()]<all[i]){
      dpl[i]=min(dpl[i],dpl[v.back()]+(i-v.back()-1)*all[v.back()]);
      v.pop_back();
    }
    v.push_back(i);
    if(tl[i]==i-1){
      dpl[i]=psl[i]=psl[tl[i]]+all[i];
    }else{
      dpl[i]+=all[i];
    }
    psl[i]=psl[tl[i]]+(i-tl[i])*all[i];
    //cout<<i<<" "<<dpl[i]<<" "<<psl[i]<<endl;
    for(auto x:allqr[i]){
      //cout<<x.first<<" "<<x.second<<" "<<i<<endl;
      long long now=i;
      while(tl[now]>=x.first){
        now=tl[now];
      }
      long long manf=psl[tl[now]]+(x.first-1-tl[now])*all[now];
      now=i;
      while(tl[now]>=x.first){
        res[x.second]=min(res[x.second],dpl[now]+(i-now)*all[now]-manf);  
        now=tl[now];
      }
      //cout<<"khor: "<<x.first<<" "<<x.second<<" "<<res[x.second]<<endl;
    }
  }
}

void solver(){
  for(long long i=n;i>=1;i--){
    if(tr[i]==i+1){
      dpr[i]=psr[i]=psr[tr[i]]+all[i];
    }else{
      dpr[i]=inf;
      for(long long j=i+1;j<tr[i];j++){
        if(tl[j]==i){
          dpr[i]=min(dpr[i],dpr[j]+(j-i-1)*all[j]);
        }
      }
      dpr[i]+=all[i];
    }
    psr[i]=psr[tr[i]]+(tr[i]-i)*all[i];
    for(auto x:allql[i]){
      long long now=i;
      while(tr[now]<=x.first){
        now=tr[now];
      }
      long long manf=psr[tr[now]]+(tr[now]-x.first-1)*all[now];
      now=i;
      while(tr[now]<=x.first){
        res[x.second]=min(res[x.second],dpr[now]+(now-i)*all[now]-manf);  
        now=tr[now];
      }
    }
  }
}

std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
                                     std::vector<int> R) {
  n=H.size();
  for(long long i=1;i<=n;i++){
    all[i]=H[i-1];
  }
  q=(long long)L.size();
  for(long long i=0;i<q;i++){
    L[i]++;
    R[i]++;
    res[i]=inf;
    allql[L[i]].push_back(make_pair(R[i],i));
    allqr[R[i]].push_back(make_pair(L[i],i));
  }
  caltltr();
  solvel();
  //cout<<"salam"<<endl;
  solver();
  vector<long long>ret;
  for(long long i=0;i<q;i++){
    if(L[i]==R[i]){
      res[i]=all[L[i]];
    }
    ret.push_back(res[i]);
  }
  return ret;
}

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