제출 #421881

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
421881		Hegdahl	모임들 (IOI18_meetings)	C++17	17 / 100	96 ms	22024 KiB

meetings

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

using namespace std;
using ll = long long;

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

struct S {
  int w = 0, l = 0, m = 0, r = 0;
  void pull(S a, S b) {
    w = a.w + b.w;
    l = (a.l == a.w ? a.l+b.l : a.l);
    m = max({a.m, a.r + b.l, b.m});
    r = (b.r == b.w ? b.r+a.r : b.r);
  }
};
S st[2*offset];

S qry(int i, int j) {
  i += offset-1;
  j += offset+1;
  S l, r;
  while (i+1 < j) {
    if (i%2 == 0) l.pull(l, st[i+1]);
    if (j%2 == 1) r.pull(st[j-1], r);
    i /= 2, j /= 2;
  }
  l.pull(l, r);
  return l;
}

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

  for (int i = 0; i < n; ++i) {
    assert(h[i] == 1 || h[i] == 2);
    st[offset+i].w = 1;
    if (h[i] == 1)
      st[offset+i].l = st[offset+i].m = st[offset+i].r = 1;
  }

  for (int i = offset-1; i > 0; --i)
    st[i].pull(st[2*i], st[2*i+1]);

  for (int qq = 0; qq < q; ++qq) {
    S qa = qry(l[qq], r[qq]);
    ans[qq] = 2*qa.w - qa.m;
  }

  return ans;
}

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