Submission #996346

#	Time	Username	Problem	Language	Result	Execution time	Memory
996346		PCTprobability	Meetings (IOI18_meetings)	C++17	41 / 100	1951 ms	130896 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class A,class B>
bool chmin(A &a,B b){
  if(a>b){
    a=b;
    return true;
  }
  return false;
}
struct S{
  int maxh;
  vector<int> radd,ladd;
  //radd <- 右に max x を付けたときそちらへ移動するときのコストの総和
  //ladd <- 左に max x を付けたときそちらへ移動するときのコストの総和
  vector<int> rc,lc;
  //lc <- (i,maxh) のときのコストの最小値
  //rc <- (maxh,i) のときのコストの最小値
  S(){
    maxh=1;
    radd.resize(21);
    ladd.resize(21);
    lc.resize(21);
    rc.resize(21);
  }
  S(int x){
    maxh=x;
    radd.resize(21);
    ladd.resize(21);
    for(int i=0;i<=20;i++){
      radd[i]=max(i,x);
      ladd[i]=max(i,x);
    }
    lc.resize(21);
    rc.resize(21);
    for(int i=0;i<=20;i++){
      lc[i]=rc[i]=1000000000;
    }
    lc[x]=rc[x]=x;
  }
};
S op(S a, S b){
  S c;
  for(int i=1;i<=20;i++){
    c.lc[i]=c.rc[i]=1000000000;
  }
  c.maxh=max(a.maxh,b.maxh);
  for(int i=1;i<=20;i++){
    c.radd[i]=a.radd[max(i,b.maxh)]+b.radd[i];
    c.ladd[i]=a.ladd[i]+b.ladd[max(i,a.maxh)];
  }
  for(int i=1;i<=20;i++){
    //a.lc[i] から
    //(i,max(a,b))
    chmin(c.lc[i],a.lc[i]+b.ladd[a.maxh]);
    //b.rc[i] から
    //(max(a,b),i)
    chmin(c.rc[i],a.radd[b.maxh]+b.rc[i]);
    //a.rc[i] から
    //(max a,max(max b,i))
    if(a.maxh==c.maxh){
      chmin(c.rc[max(b.maxh,i)],a.rc[i]+b.ladd[i]);
    }
    else{
      chmin(c.lc[a.maxh],a.rc[i]+b.ladd[i]);
    }
    //b.lc[i] から
    //(max(max a,i),max b)
    if(b.maxh==c.maxh){
      chmin(c.lc[max(a.maxh,i)],b.lc[i]+a.radd[i]);
    }
    else{
      chmin(c.rc[b.maxh],b.lc[i]+a.radd[i]);
    }
  }
  return c;
}
S e(){
  return S();
}
struct segtree{
  int n;
  vector<S> node;
  segtree(int n_){
    n=1;
    while(n<n_){
      n*=2;
    }
    node.resize(2*n);
  }
  void set(int i,S x){
    i+=n;
    node[i]=x;
    while(i/2){
      i/=2;
      node[i]=op(node[2*i],node[2*i+1]);
    }
  }
  S prod(int l,int r,int a,int b,int k){
    if(r<=a||b<=l) return e();
    if(l<=a&&b<=r) return node[k];
    return op(prod(l,r,a,(a+b)/2,2*k),prod(l,r,(a+b)/2,b,2*k+1));
  }
  S prod(int l,int r){
    return prod(l,r,0,n,1);
  }
};
std::vector<long long> minimum_costs(std::vector<int> h, std::vector<int> l,std::vector<int> r) {
  int n=h.size();
  int q=l.size();
  vector<ll> ans(q,1ll<<60);
  for(int i=0;i<n;i++) assert(h[i]<=20);
  segtree seg(n);
  for(int i=0;i<n;i++) seg.set(i,S(h[i]));
  for(int i=0;i<q;i++){
    S v=seg.prod(l[i],r[i]+1);
    //cout<<v.maxh<<endl;
    for(int j=1;j<=20;j++){
      //cout<<v.lc[j]<<" "<<v.rc[j]<<endl;
      chmin(ans[i],v.lc[j]);
      chmin(ans[i],v.rc[j]);
    }
  }
  return ans;
}

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