Submission #425937

#	Time	Username	Problem	Language	Result	Execution time	Memory
425937		MarcoMeijer	Meetings (IOI18_meetings)	C++14	60 / 100	712 ms	392260 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef vector<ii> vii;

#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define RE(a,b) REP(a,0,b)
#define RE1(a,b) REP(a,1,b+1)
#define FOR(a,b) for(auto& a : b)
#define pb push_back
#define fi first
#define se second
#define all(a) a.begin(), a.end()

const int MXH = 21;
const int N = (1<<17);

struct T {
  int resl[MXH], resr[MXH];
  int minl[MXH], minr[MXH];
  int maxh;
};
T combine(const T& l, const T& r) {
  if(l.maxh == 0) return r;
  if(r.maxh == 0) return l;
  T res;
  res.maxh = max(l.maxh, r.maxh);
  RE(i,MXH) res.minl[i] = l.minl[i] + r.minl[max(i,l.maxh)];
  RE(i,MXH) res.minr[i] = r.minr[i] + l.minr[max(i,r.maxh)];
  RE(i,MXH) res.resl[i] = res.resr[i] = 1e9;
  RE(i,res.maxh+1) {
    res.resl[i     ] = min(res.resl[i], l.resl[i] + r.minl[l.maxh]);
    res.resr[i     ] = min(res.resr[i], r.resr[i] + l.minr[r.maxh]);
    if(l.maxh == res.maxh && r.maxh != res.maxh)
      res.resr[max(r.maxh,i)] = min(res.resr[max(r.maxh,i)], l.resr[i] + r.minl[i]);
    else
      res.resl[max(l.maxh,i)] = min(res.resl[max(l.maxh,i)], l.resr[i] + r.minl[i]);
    if(l.maxh != res.maxh && r.maxh == res.maxh)
      res.resl[max(l.maxh,i)] = min(res.resl[max(l.maxh,i)], r.resl[i] + l.minr[i]);
    else
      res.resr[max(r.maxh,i)] = min(res.resr[max(r.maxh,i)], r.resl[i] + l.minr[i]);
  }
  return res;
}
T createSingle(int x) {
  T res;
  res.maxh = x;
  RE(i,MXH) res.resl[i]=res.resr[i]=1e9;
  res.resl[x] = res.resr[x] = x;
  RE(i,MXH) res.minl[i]=res.minr[i]=max(x,i);
  return res;
}
T createEmpty() {
  T res;
  res.maxh = 0;
  return res;
}

T seg[N*2];
int h[N];
void buildSeg(int p=1, int l=0, int r=N-1) {
  if(l == r) {
    seg[p] = createSingle(h[l]);
    return;
  }
  int m=(l+r)/2;
  buildSeg(p*2  ,l  ,m);
  buildSeg(p*2+1,m+1,r);
  seg[p] = combine(seg[p*2], seg[p*2+1]);
}
T getSeg(int i, int j, int p=1, int l=0, int r=N-1) {
  if(j < l || i > r) return createEmpty();
  if(i <= l && j >= r) return seg[p];
  int m=(l+r)/2;
  T a = getSeg(i,j,p*2  ,l  ,m);
  T b = getSeg(i,j,p*2+1,m+1,r);
  return combine(a,b);
}

vll minimum_costs(vi H, vi L, vi R) {
  int n = H.size();
  int q = L.size();

  if(n <= 5000 && q <= 5000) {
    vector<vll> costL, costR;
    RE(i,2) (i?costL:costR).assign(n,vll(n,0));
    RE(i,n) {
      ll mx = 0;
      ll res = 0;
      REP(j,i,n) {
        mx = max<ll>(mx,H[j]);
        res += mx;
        costR[j][i] = res;
      }
      mx = res = 0;
      REV(j,0,i+1) {
        mx = max<ll>(mx,H[j]);
        res += mx;
        costL[j][i] = res;
      }
    }

    vll C(q,1e18);
    RE(cq,q) {
      int l=L[cq], r=R[cq];
      REP(i,l,r+1) {
        C[cq] = min(C[cq], costL[l][i] + costR[r][i] - H[i]);
      }
    }
    return C;
  } else {
    RE(i,n) h[i]=H[i];
    buildSeg();
    vll C(q,1e18);
    RE(cq,q) {
      int l=L[cq], r=R[cq];
      T res = getSeg(l,r);
      RE(i,MXH) {
        C[cq] = min<ll>(C[cq], min(res.resr[i], res.resl[i]));
      }
    }
    return C;
  }
}

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