Submission #421915

#	Time	Username	Problem	Language	Result	Execution time	Memory
421915		Hegdahl	Meetings (IOI18_meetings)	C++17	0 / 100	5592 ms	3524 KiB

meetings

#include <bits/stdc++.h>
#include "meetings.h"

using namespace std;
using ll = long long;

const ll INF = 1LL<<60;

const int mxN = 75e4;
const int offset = 2<<__lg(mxN-1);

int n, q;
vector<int> h;

ll val[2*offset];
ll lazy[offset];

int push(int I, int l, int r) {
  if (lazy[I]) {
    val[2*I] += lazy[I];
    val[2*I+1] += lazy[I];
    if (2*I < offset) {
      lazy[2*I] += lazy[I];
      lazy[2*I+1] += lazy[I];
    }
    lazy[I] = 0;
  }

  return l + (r-l+1)/2;
}

ll qry(int i, int j, int I = 1, int l = 0, int r = mxN-1) {
  if (i > r || j < l) return INF;
  if (i <= l && j >= r) return val[I];
  int mid = push(I, l, r);
  ll ans = INF;
  if (i < mid) ans = min(ans, qry(i, j, 2*I, l, mid-1));
  if (j >= mid) ans = min(ans, qry(i, j, 2*I+1, mid, r));
  return ans;
}

void upd(int i, int j, ll x, int I = 1, int l = 0, int r = mxN-1) {
  if (i > r || j < l) return;
  if (i <= l && j >= r) {
    val[I] += x;
    if (I < offset) lazy[I] += x;
    return;
  }
  int mid = push(I, l, r);
  if (i < mid) upd(i, j, x, 2*I, l, mid-1);
  if (j >= mid) upd(i, j, x, 2*I+1, mid, r);
  val[I] = min(val[2*I], val[2*I+1]);
}

void insert(int i) {
  for (int j = i, mx = h[i]; j < n; ++j) {
    mx = max(mx, h[j]);
    upd(j, j, mx);
  }
  for (int j = i-1, mx = h[i]; j >= 0; --j) {
    mx = max(mx, h[j]);
    upd(j, j, mx);
  }
}

void erase(int i) {
  for (int j = i, mx = 0; j < n; ++j) {
    mx = max(mx, h[j]);
    upd(j, j, -mx);
  }
  for (int j = i-1, mx = 0; j >= 0; --j) {
    mx = max(mx, h[j]);
    upd(j, j, -mx);
  }
}

ll solve(int L, int R) {
  static int CL = 0, CR = -1;
  while (CR < R) insert(++CR);
  while (CL > L) insert(--CL);
  while (CR > R) erase(CR--);
  while (CL < L) erase(CL++);
  return qry(L, R);
}

vector<ll> minimum_costs(vector<int> h_, vector<int> l, vector<int> r) {
  h = h_;
  n = (int)h.size();
  q = (int)l.size();
  vector<ll> ans(q);

  const int R = sqrt(n);

  vector<int> s(q);
  iota(s.begin(), s.end(), 0);
  sort(s.begin(), s.end(), [&](int i, int j) -> bool {
    if (l[i]/R != l[j]/R) return l[i]/R < l[j]/R;
    return (r[i]>r[j])^l[i];
  });

  for (int qq : s)
    ans[qq] = solve(l[qq], r[qq]);

  return ans;
}

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