제출 #1052677

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1052677		amirhoseinfar1385	Meetings (IOI18_meetings)	C++17	60 / 100	642 ms	310380 KiB

meetings

#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
const long long maxn=100000+10,lg=20,kaf=(1<<lg),maxr=1e6+5;
long long ezaf=0,all[maxn],n,dpl[maxn],dpr[maxn],tr[maxn],tl[maxn],psl[maxn],psr[maxn],inf=1e16,ezafq[maxn];
vector<pair<long long,long long>>allql[maxn],allqr[maxn];
long long q,res[maxn];
struct func{
  long long x0,y0,sh,ta,wa;
  func(){
    x0=0;
    y0=inf;
    sh=0;
    ta=inf;
    wa=inf;
  }
  long long get(long long x){
    return (x-x0)*sh+y0;
  }
}fakefunc;
 
struct lichao{
  struct node{
    func f;
    long long cl,cr;
    node(){
      cl=cr=-1;
    }
  }fakenode;
  vector<node>alln;
  long long te=1;
  lichao(){
    te=1;
    alln.resize(1);
  }
  void clear(){
    for(long long i=0;i<te;i++){
      alln[i]=fakenode;
    }
    te=1;
  }
  long long getl(long long i){
    if(alln[i].cl==-1){
      if((long long)alln.size()==te){
        alln.push_back(fakenode);
      }
      alln[i].cl=te;
      te++;
    }
    return alln[i].cl;
  }
  long long getr(long long i){
    if(alln[i].cr==-1){
      if((long long)alln.size()==te){
        alln.push_back(fakenode);
      }
      alln[i].cr=te;
      te++;
    }
    return alln[i].cr;
  }
  long long pors(long long i,long long l,long long r,long long x){
    if(i==-1){
      return inf;
    }
    long long ret=alln[i].f.get(x);
    long long mid=(l+r)>>1;
    if(r==l+1){
      return ret;
    }
    if(x<mid){
      ret=min(ret,pors(alln[i].cl,l,mid,x));
    }else{
      ret=min(ret,pors(alln[i].cr,mid,r,x));
    }
    return ret;
  }
  void ins(long long i,long long l,long long r,func fa){
    if(alln[i].f.sh==0){
       swap(alln[i].f,fa);
       return ;
    }
    if(alln[i].f.get(l)>fa.get(l)){
      swap(alln[i].f,fa);
    }
    if(r==l+1){
      return ;
    } 
    long long mid=(l+r)>>1;
    if(alln[i].f.get(mid)<=fa.get(mid)){
      return ins(getr(i),mid,r,fa);
    }else{
      swap(alln[i].f,fa);
      return ins(getl(i),l,mid,fa);
    }
  }
}lch;

bool cmp(pair<long long,func>a,pair<long long,func>b){
  if(a.first!=b.first){
    return a.first<b.first;
  }
  if(a.second.x0!=b.second.x0){
    return a.second.x0<b.second.x0;
  }  
  if(a.second.sh!=b.second.sh){
    return a.second.sh<b.second.sh;
  }
  return a.second.y0<b.second.y0;
}
 
struct segment{
  vector<pair<long long,pair<long long,long long>>>segq[(1<<(lg+1))];
  vector<pair<long long,func>>segi[(1<<(lg+1))];
  void clear(){
    for(long long i=0;i<(1<<(lg+1));i++){
      segq[i].clear();
      segi[i].clear();
    }
  }
  void insq(long long i,pair<long long,pair<long long ,long long>>w){
    i+=kaf;
    while(i>0){
      segq[i].push_back(w);
      i>>=1;
    }
  }
  void insi(long long i,long long l,long long r,long long tl,long long tr,pair<long long,func>w){
    if(l>r||l>tr||r<tl||tl>tr){
      return ;
    }
    if(l>=tl&&r<=tr){
      segi[i].push_back(w);
      return ;
    }
    long long m=(l+r)>>1;
    insi((i<<1),l,m,tl,tr,w);
    insi((i<<1)^1,m+1,r,tl,tr,w);
    return ;
  }
  void calc(long long w){
    lichao lich;
    for(long long i=0;i<(1<<(lg+1));i++){
      sort(segq[i].begin(),segq[i].end());
      sort(segi[i].begin(),segi[i].end(),cmp);
      lich.clear();
      if(w==0){
        long long i1=(long long)segq[i].size()-1,i2=(long long)segi[i].size()-1;
        while(i1>=0&&i2>=0){
          if(segq[i][i1].first<=segi[i][i2].first){
            lich.ins(0,0,maxr-1,segi[i][i2].second);
            i2--;
          }else{
            res[segq[i][i1].second.second]=min(res[segq[i][i1].second.second],lich.pors(0,0,maxr,segq[i][i1].second.first)+ezafq[segq[i][i1].second.second]);
            i1--;
          }
        }
        while(i1>=0){
           res[segq[i][i1].second.second]=min(res[segq[i][i1].second.second],lich.pors(0,0,maxr,segq[i][i1].second.first)+ezafq[segq[i][i1].second.second]);
           i1--;
        }
      }else{
        long long i1=0,i2=0;
        while(i1<(long long)segq[i].size()&&i2<(long long)segi[i].size()){
          if(segq[i][i1].first>=segi[i][i2].first){
            lich.ins(0,0,maxr-1,segi[i][i2].second);
            i2++;
          }else{
            res[segq[i][i1].second.second]=min(res[segq[i][i1].second.second],lich.pors(0,0,maxr,segq[i][i1].second.first)+ezafq[segq[i][i1].second.second]);
            i1++;
          }
        }
        while(i1<(long long)segq[i].size()){
           res[segq[i][i1].second.second]=min(res[segq[i][i1].second.second],lich.pors(0,0,maxr,segq[i][i1].second.first)+ezafq[segq[i][i1].second.second]);
           i1++;
        }
      }
    }
  }
}seg;
 
void caltltr(){
  vector<long long>v;
  all[0]=inf;
  all[n+1]=inf;
  v.push_back(0);
  for(long long i=1;i<=n+1;i++){
    while((int)v.size()>1&&all[v.back()]<=all[i]){
      tr[v.back()]=i;
      v.pop_back();
    }
    v.push_back(i);
  }
  v.clear();
  v.push_back(n+1);
  for(long long i=n;i>=0;i--){
    while((int)v.size()>1&&all[v.back()]<all[i]){
      tl[v.back()]=i;
      v.pop_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];
    func fa;
    fa.x0=i;
    fa.y0=dpl[i];
    fa.sh=all[i];
    seg.insi(1,0,kaf-1,i,tr[i]-1,make_pair(i,fa));
    for(auto x:allqr[i]){
      long long p=lower_bound(v.begin(),v.end(),x.first)-v.begin();
      long long now=i;
      now=v[p];
      long long manf=psl[tl[now]]+(x.first-1-tl[now])*all[now];
      ezafq[x.second]=-manf;
      seg.insq(i,make_pair(now+1,make_pair(i,x.second)));
      //res[x.second]=min(res[x.second],seg.pors(1,0,kaf-1,p+1,(long long)v.size()-1,i)-manf);
    }
  }
  seg.calc(0);
  seg.clear();
}
 
void solver(){
  vector<long long>v;
  deque<long long>tofv;
  seg.clear();
  v.push_back(n+1);
  tofv.push_front(n+1);
  for(long long i=n;i>=1;i--){
    dpr[i]=inf;
    while(all[v.back()]<all[i]){
      dpr[i]=min(dpr[i],dpr[v.back()]+(v.back()-i-1)*all[v.back()]);
      v.pop_back();
      tofv.pop_front();
    }
    tofv.push_front(i);
    v.push_back(i);
    if(tr[i]==i+1){
      dpr[i]=psr[i]=psr[tr[i]]+all[i];
    }else{
      dpr[i]+=all[i];
    }
    psr[i]=psr[tr[i]]+(tr[i]-i)*all[i];
    func fa;
    fa.x0=i;
    fa.y0=dpr[i];
    fa.sh=-all[i];
    //cout<<"ins: "<<fa.x0<<" "<<fa.sh<<" "<<fa.y0<<" "<<tl[i]+1<<" "<<i<<endl;
    seg.insi(1,0,kaf-1,tl[i]+1,i,make_pair(i,fa));
    //seg.ins(v.size()-1,fa);
    for(auto x:allql[i]){
      long long p=lower_bound(tofv.begin(),tofv.end(),x.first+1)-tofv.begin();
      long long now=i;
      if(p==0||p-1>=(long long)tofv.size()){
        continue;
      }
      now=tofv[p-1];
      long long manf=psr[tr[now]]+(tr[now]-x.first-1)*all[now];
      ezafq[x.second]=-manf;
      seg.insq(i,make_pair(now-1,make_pair(i,x.second)));
    //  cout<<i<<" "<<now<<" "<<x.first<<" "<<x.second<<endl;
     /* now=i;
      while(tr[now]<=x.first){
        res[x.second]=min(res[x.second],dpr[now]+(now-i)*all[now]-manf);  
        now=tr[now];
      }*/
    }
  }
  seg.calc(1);
}
 
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();
  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: 17 / 17
• Subtask 4: 24 / 24
• Subtask 5: 0 / 40