제출 #1244834

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1244834		Boas	Meetings (IOI18_meetings)	C++20	17 / 100	81 ms	11764 KiB

meetings

#include "meetings.h"

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

#define int long long
#define pb push_back
#define sz(x) (int)x.size()
#define ALL(x) begin(x), end(x)
#define loop(n, i) for (int i = 0; i < n; i++)
#define rev(n, i) for (int i = n - 1; i >= 0; i--)

typedef signed i32;
typedef long long i64;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<i32> vi32;
typedef vector<vi32> vvi32;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<vii> vvii;

struct node
{
  int cnt = 0, cntl = 0, cntr = 0, sz = 0;
  node operator+(node b)
  {
    int cntl2 = cntl, cntr2 = b.cntr;
    if (cntl == sz)
      cntl2 += b.cntl;
    if (b.cntr == b.sz)
      cntr2 += cntr;
    return {max({cnt, b.cnt, cntr + b.cntl}), cntl2, cntr2, sz + b.sz};
  };
  void operator+=(node b) { *this = *this + b; }
};

vector<node> s;

node query(int i, int l, int r, int ql, int qr)
{
  if (qr < l || r < ql)
    return {};
  if (ql <= l && r <= qr)
    return s[i];
  int m = (l + r) / 2;
  node resl = query(2 * i, l, m, ql, qr);
  node resr = query(2 * i + 1, m + 1, r, ql, qr);
  node res = resl + resr;
  return res;
}

vi minimum_costs(vi32 H, vi32 L, vi32 R)
{
  int Q = sz(L);
  vi C(Q);
  int N = sz(H);
  int treeN = 1;
  while (treeN < N)
    treeN *= 2;
  s.assign(2 * treeN, {});
  loop(N, i)
  {
    s[i + treeN].sz = 1;
    if (H[i] == 1)
      s[i + treeN] = {1, 1, 1, 1};
  }
  rev(treeN, i)
  {
    s[i] = s[2 * i] + s[2 * i + 1];
  }
  for (int j = 0; j < Q; ++j)
  {
    int l = L[j];
    int r = R[j];
    int res = 2 * (r - l + 1) - query(1, 0, treeN - 1, l, r).cnt;
    C[j] = res;
  }
  return C;
}

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