Submission #606662

#	Time	Username	Problem	Language	Result	Execution time	Memory
606662		piOOE	Meetings (IOI18_meetings)	C++17	36 / 100	5521 ms	7504 KiB

meetings

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

using namespace std;

using ll = long long;

struct node {
  int pref = 0, suf = 0, ans = 0, sz = 0;
  node() = default;
  node(int a) {
    if (a == 1) {
      pref = suf = ans = 1;
    }
    sz = 1;
  }
};

node operator+(node a, node b) {
  node res;
  res.sz = a.sz + b.sz;
  res.pref = (a.pref == a.sz ? a.sz + b.pref : a.pref);
  res.suf = (b.suf == b.sz ? b.sz + a.suf : b.suf);
  res.ans = max({res.pref, res.suf, a.ans, b.ans, a.suf + b.pref});
  return res;
}

vector<node> tree;

int sz = 1;

void init(vector<int> &a) {
  int n = (int)a.size();
  sz = 1;
  while (sz < n) {
    sz <<= 1;
  }
  tree.assign(sz << 1, {});
  for (int i = 0; i < n; ++i) {
    tree[i + sz] = node(a[i]);
  }
  for (int i = sz - 1; i > 0; --i) {
    tree[i] = tree[i << 1] + tree[i << 1 | 1];
  }
}

node get(int l, int r, int x = 1, int lx = 0, int rx = sz) {
  if (l >= rx || lx >= r) return {};
  if (l <= lx && rx <= r) {
    return tree[x];
  }
  int mid = (lx + rx) >> 1;
  return get(l, r, x << 1, lx, mid) + get(l, r, x << 1 | 1, mid, rx);
}

vector<ll> minimum_costs(vector<int> a, vector<int> L, vector<int> R) {
  int n = (int) a.size();
  int q = (int) L.size();
  vector<ll> ans(q, LLONG_MAX);
  if (*max_element(a.begin(), a.end()) <= 2) {
    init(a);
    for (int i = 0; i < q; ++i) {
      ans[i] = (R[i] - L[i] + 1) * 2 - get(L[i], R[i] + 1).ans;
    }
    return ans;
  } else {
    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] = LLONG_MAX;
      for (int i = l; i <= r; ++i) {
        ans[t] = min(ans[t], pref[i] + suf[i] - a[i]);
      }
    }
    return ans;
  }
}

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