Submission #253200

#	Time	Username	Problem	Language	Result	Execution time	Memory
253200		rama_pang	Rabbit Carrot (LMIO19_triusis)	C++14	100 / 100	789 ms	157048 KiB

triusis

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

using lint = long long;

struct Node {
  int val = 1e9;
  int lazy = 0;
  int lc = 0;
  int rc = 0;
  Node() {}
  Node(int val) : val(val) {}
} d[int(1e7)];

int NewNode() {
  static int ptd = 2;
  return ptd++;
}

void Apply(int &n, int x) {
  if (n == 0) n = NewNode();
  d[n].val += x;
  d[n].lazy += x;
}

void Push(int &n, int &lc, int &rc) {
  if (d[n].lazy > 0) {
    Apply(lc, d[n].lazy);
    Apply(rc, d[n].lazy);
    d[n].lazy = 0;
  }
}

void Pull(int n, int lc, int rc) {
  d[n].val = min(d[lc].val, d[rc].val);
}

void Update(int &n, lint tl, lint tr, lint p, int x) {
  if (n == 0) n = NewNode();
  if (tl == tr) {
    d[n].val = min(d[n].val, x);
    return;
  }
  lint md = (tl + tr) / 2;
  Push(n, d[n].lc, d[n].rc);
  if (p <= md) {
    Update(d[n].lc, tl, md, p, x);
  } else {
    Update(d[n].rc, md + 1, tr, p, x);
  }
  Pull(n, d[n].lc, d[n].rc);
}

int Query(int n, lint tl, lint tr, lint l, lint r) {
  if (n == 0 || r < tl || tr < l || tl > tr || l > r) return 1e9;
  if (l <= tl && tr <= r) return d[n].val;
  lint md = (tl + tr) / 2;
  Push(n, d[n].lc, d[n].rc);
  return min(Query(d[n].lc, tl, md, l, r), Query(d[n].rc, md + 1, tr, l, r));
}

void Add(int &n, lint tl, lint tr, lint l, lint r, int x) {
  if (r < tl || tr < l || tl > tr || l > r) return;
  if (n == 0) n = NewNode();
  if (l <= tl && tr <= r) return Apply(n, x);
  lint md = (tl + tr) / 2;
  Push(n, d[n].lc, d[n].rc);
  Add(d[n].lc, tl, md, l, r, x);
  Add(d[n].rc, md + 1, tr, l, r, x);
  Pull(n, d[n].lc, d[n].rc);
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);

  int N, M;
  cin >> N >> M;

  lint base = 1e11;
  lint inf = 1e12;
  int root = NewNode();
  Update(root, 0, inf, base, 0);

  for (int i = 0; i < N; i++) {
    int a;
    cin >> a;
    auto v = Query(root, 0, inf, max(a - M, 0) + base, inf);
    base -= M;
    Add(root, 0, inf, base, inf, 1);
    Update(root, 0, inf, base + a, v);
  }
  
  cout << Query(root, 0, inf, base, inf) << "\n";
  return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 28 / 28
• Subtask 4: 37 / 37