Submission #997772

#	Time	Username	Problem	Language	Result	Execution time	Memory
997772		lucascgar	Rabbit Carrot (LMIO19_triusis)	C++17	100 / 100	20 ms	2284 KiB

triusis

#include <bits/stdc++.h>

#define double long double // avoid maybe precision errors

// #pragma GCC optimize("Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

using namespace std;

/*
INVERTER PROBLEMA É ÚTIL:
LEAST AMOUNT TO MAKE FIXED:
LARGEST SUBSEQUENCE OF FIXED PILLARS

last fixed i

max height for j = h[i] + (j-i)*M

turn h[i] into factor of m and subtract from i (have to use double but it works):
i = i - (double)h[i]/m

double precision errors?? apparently not important enough
there is probably a way to do this without using doubles (preferrable):
-   i - h[i]/m becomes i*m - h[i]
*/

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); // overclock random

typedef pair<int,int> pii;
typedef pair<long long, long long> pll;
typedef pair<double, double> pdd;

const int MAXN = 2e5+10;

int h[MAXN];

signed main(){
    std::ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    // freopen("test.in", "r", stdin);
    // freopen("test.out", "w", stdout);
    // cout << fixed << setprecision(12);

    int n, m;
    cin >> n >> m;

    // vector<double> lis;  // increasing subsequence of positions: lis[i] = last j position of subsequence of size i
    vector<int> lis; // same thing but remove division by multiplying both terms by m

    for (int i=1;i<=n;i++){  // try to add you to some sequence if you are fixed
        cin >> h[i];
        if (h[i] > m*i) continue;  // all values must be reachable

        // double tg = i - (double)h[i]/m;  // obligatory >=0
        int tg = i*m - h[i];

        if (lis.empty()){
            lis.push_back(tg);
        }else{

            int p = upper_bound(lis.begin(), lis.end(), tg) - lis.begin();

            if (p == lis.size()) lis.push_back(tg);
            else lis[p] = tg;

        }

    }

    cout << n-lis.size() << "\n";

    return 0;
}

Compilation message (stderr)

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

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