제출 #608209

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
608209		piOOE	Meetings (IOI18_meetings)	C++17	60 / 100	5542 ms	56892 KiB

meetings

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

using namespace std;

using ll = long long;

const ll inf = 3e18;

vector<ll> smart20(vector<int> a, vector<int> L, vector<int> R) {
  int n = (int) a.size();
  int q = (int) L.size();
  vector<ll> ans(q, inf);

  int logn = __lg(n) + 1;
  vector<vector<int>> st(logn);
  vector<vector<ll>> sp(logn);
  st[0] = a;
  for (int i = 1; i < logn; ++i) {
    st[i].resize(n - (1 << i) + 1);
    for (int j = 0; j <= (n - (1 << i)); ++j) {
      st[i][j] = max(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
    }
  }
  auto get = [&](int l, int r) {
    if (!(r > l && l >= 0 && r <= n)) {
      assert(false);
    }
    int lg = __lg(r - l);
    return max(st[lg][l], st[lg][r - (1 << lg)]);
  };
  int mx = *max_element(a.begin(), a.end());
  vector<int> g[mx + 1];
  vector pref(mx + 1, vector<ll>(n)), suf(mx + 1, vector<ll>(n));
  for (int i = 0; i < n; ++i) {
    g[a[i]].push_back(i);
  }
  for (int i = 0; i < n; ++i) {
    auto FirstBigger = [&](int x) {
      int l = -1, r = i;
      while (l + 1 < r) {
        int mid = (l + r) >> 1;
        if (get(mid, i + 1) > x) {
          l = mid;
        } else {
          r = mid;
        }
      }
      return l;
    };
    int j = FirstBigger(a[i]);
    ll val = a[i] * (i - j) + (j == -1 ? 0 : pref[0][j]);
    for (int x = 0; x <= a[i]; ++x) {
      pref[x][i] = val;
    }
    for (int x = a[i] + 1; x <= mx; ++x) {
      j = FirstBigger(x);
      pref[x][i] = x * (i - j) + (j == -1 ? 0 : pref[0][j]);
    }
  }
  for (int i = n - 1; i > -1; --i) {
    auto FirstBigger = [&](int x) {
      int l = i, r = n + 1;
      while (l + 1 < r) {
        int mid = (l + r) >> 1;
        if (get(i, mid) > x) {
          r = mid;
        } else {
          l = mid;
        }
      }
      return l;
    };
    int j = FirstBigger(a[i]);
    ll val = a[i] * (j - i) + (j == n ? 0 : suf[0][j]);
    for (int x = 0; x <= a[i]; ++x) {
      suf[x][i] = val;
    }
    for (int x = a[i] + 1; x <= mx; ++x) {
      j = FirstBigger(x);
      suf[x][i] = x * (j - i) + (j == n ? 0 : suf[0][j]);
    }
  }
  sp[0].resize(n);
  for (int i = 0; i < n; ++i) {
    sp[0][i] = pref[a[i]][i] + suf[a[i]][i] - a[i];
  }
  for (int i = 1; i < logn; ++i) {
    sp[i].resize(n - (1 << i) + 1);
    for (int j = 0; j <= (n - (1 << i)); ++j) {
      sp[i][j] = min(sp[i - 1][j], sp[i - 1][j + (1 << (i - 1))]);
    }
  }
  for (int t = 0; t < q; ++t) {
    int l = L[t], r = R[t];
    vector<int> nxt;
    for (int x = 1; x <= mx; ++x) {
      auto it = lower_bound(g[x].begin(), g[x].end(), l);
      if (it != g[x].end() && *it <= r) {
        nxt.push_back(*it);
        it = upper_bound(g[x].begin(), g[x].end(), r);
        nxt.push_back(*prev(it));
      }
    }
    sort(nxt.begin(), nxt.end());
    nxt.resize(unique(nxt.begin(), nxt.end()) - nxt.begin());
    int m = (int) nxt.size();
    auto get_min = [&](int l, int r) {
      if (!(r > l && l >= 0 && r <= n)) {
        return inf;
      }
      int lg = __lg(r - l);
      return min(sp[lg][l], sp[lg][r - (1 << lg)]);
    };
    for (int id = 0; id < m; ++id) {
      int i = nxt[id];
      int right = id == m - 1 ? r + 1 : nxt[id + 1];
      {
        ans[t] = min(ans[t], (pref[a[i]][i] + suf[a[i]][i] - a[i]) - (l == 0 ? 0 : pref[get(l, i + 1)][l - 1]) -
                             (r == n - 1 ? 0 : suf[get(i, r + 1)][r + 1]));
      }
      if (right <= r) {
        ans[t] = min(ans[t], get_min(i + 1, right) - (l == 0 ? 0 : pref[get(l, i + 1)][l - 1]) -
                             (r == n - 1 ? 0 : suf[get(i + 1, r + 1)][r + 1]));
      }
    }
  }
  return ans;
}

vector<ll> stupid(vector<int> a, vector<int> L, vector<int> R) {
  int n = (int) a.size();
  int q = (int) L.size();
  vector<ll> ans(q, inf);
  vector<ll> pref(n), suf(n);
  for (int t = 0; t < q; ++t) {
    int l = L[t], r = R[t];
    vector<int> stk;
    ll sum = 0;
    for (int i = l; i <= r; ++i) {
      while (!stk.empty() && a[stk.back()] <= a[i]) {
        int j = stk.back();
        stk.pop_back();
        sum += (a[i] - a[j]) * (ll) (j - (stk.empty() ? l - 1 : stk.back()));
      }
      stk.push_back(i);
      sum += a[i];
      pref[i] = sum;
    }
    stk.clear();
    sum = 0;
    for (int i = r; i >= l; --i) {
      while (!stk.empty() && a[stk.back()] <= a[i]) {
        int j = stk.back();
        stk.pop_back();
        sum += (a[i] - a[j]) * (ll) ((stk.empty() ? r + 1 : stk.back()) - j);
      }
      stk.push_back(i);
      sum += a[i];
      suf[i] = sum;
    }
    ans[t] = inf;
    for (int i = l; i <= r; ++i) {
      ans[t] = min(ans[t], pref[i] + suf[i] - a[i]);
    }
  }
  return ans;
}

vector<ll> minimum_costs(vector<int> a, vector<int> L, vector<int> R) {
  if (*max_element(a.begin(), a.end()) <= 20) {
    return smart20(a, L, R);
  } else {
    return stupid(a, L, R);
  }
}

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