Submission #647949

#	Time	Username	Problem	Language	Result	Execution time	Memory
647949		huyle	Rabbit Carrot (LMIO19_triusis)	C++17	100 / 100	35 ms	6832 KiB

triusis

#include <bits/stdc++.h>
using i64 = long long;
#ifdef DEBUG
#include "debug.h"
#else
#define debug(...) 69
#endif

int32_t main() {
  std::cin.tie(0)->sync_with_stdio(0);
  std::cin.exceptions(std::cin.failbit);
  int n, m;
  std::cin >> n >> m;
  std::vector<i64> a, lis;
  for (int i = 0; i < n; ++i) {
    i64 tmp;
    std::cin >> tmp;
    tmp = 1LL * m * (i + 1) - tmp;
    if (tmp >= 0) a.push_back(tmp);
  }
  for (int i = 0; i < (int)a.size(); ++i) {
    auto pos = std::upper_bound(lis.begin(), lis.end(), a[i]) - lis.begin();
    if (pos == lis.size())
      lis.push_back(a[i]);
    else
      lis[pos] = a[i];
  }
  std::cout << n - lis.size() << "\n";
}

Compilation message (stderr)

triusis.cpp: In function 'int32_t main()':
triusis.cpp:23:13: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     if (pos == lis.size())
      |         ~~~~^~~~~~~~~~~~~

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