Submission #1150006

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150006		draiiiiiiiiiiid	Rabbit Carrot (LMIO19_triusis)	C++20	0 / 100	1 ms	328 KiB

triusis

#include <bits/stdc++.h>
// #include <ext/rope>
using namespace std;
// using namespace __gnu_cxx;
// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;
// template <class T>
// using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define int long long
const int MXV = (1LL << 58) - 1;

void dbg(vector<int> &v) { for(int k: v) cout << k << " "; }
void dbg(map<int, int> &v) { for(auto [a, b]: v) cout << a << " " << b << '\n'; }
void dbg(set<int> &v) { for(int k: v) cout << k << " "; }
struct DSU {
  vector<int> par, sz;
  DSU(int n) {
    par.resize(n+1);
    sz.resize(n+1, 1);
    for(int i = 0 ; i <= n ; i++) par[i] = i;
  }

  int pfind(int v) {
    if(v == par[v]) return v;
    else return par[v] = pfind(par[v]);
  }

  void sunion(int a, int b) {
    a = pfind(a);
    b = pfind(b);
    if(a == b) return;
    if(sz[a] > sz[b]) swap(a, b);
    par[b] = a;
    sz[a] += sz[b];
  }
};

void solve() {
  int n, m; cin >> n >> m;
  vector<int> v(n+1, 0);
  for(int i = 1 ; i <= n ; i++) cin >> v[i];
  int r = 0;
  for(int i = 1 ; i <= n ; i++) {
    if(v[i] - v[i-1] > m) {
      v[i] = v[i-1] + m;
      r++;
    }
  }

  cout << r << endl;
}

signed main() {
  // int t; cin >> t;
  int t = 1;
  while(t--) solve();
}

// think greedy first, Div2AB usually are some sort of greedy, super simple usually
// C on Div2 or E on Div3/4 require more thinking but still not too hard
// for later problems, think about data structures like segment tree and ordered set
// do smth instead of nothing and stay organized
// WRITE STUFF DOWN
// DON'T GET STUCK ON ONE APPROACH

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