Submission #522584

#	Time	Username	Problem	Language	Result	Execution time	Memory
522584		ddy888	Rabbit Carrot (LMIO19_triusis)	C++17	100 / 100	36 ms	5344 KiB

triusis

#undef _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long 
#define pb push_back
#define fi first
#define si second
#define ar array
typedef pair<int,int> pi;
typedef tuple<int,int,int> ti;  
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {cerr << " " << to_string(H);debug_out(T...);}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)

const int INF = 1e18;
int N, M, lis;
int A[200010], dp[200010];

signed main() {
    fast;
    cin >> N >> M;
    for (int i = 1; i <= N; ++i) {
        cin >> A[i];
        A[i] -= (i * M);
    }
    A[0] = 0;
    for (int i = 0; i <= 200010; ++i) dp[i] = INF;
    for (int i = N; i >= 0; --i) {
        int p = upper_bound(dp + 1, dp + N + 2, A[i]) - dp;
        dp[p] = A[i];
        // debug(A[i], p);
        lis = p;
    }
    cout << N - lis + 1;
    return 0;
}

Compilation message (stderr)

triusis.cpp: In function 'int main()':
triusis.cpp:29:45: warning: iteration 200010 invokes undefined behavior [-Waggressive-loop-optimizations]
   29 |     for (int i = 0; i <= 200010; ++i) dp[i] = INF;
      |                                       ~~~~~~^~~~~
triusis.cpp:29:23: note: within this loop
   29 |     for (int i = 0; i <= 200010; ++i) dp[i] = INF;
      |                     ~~^~~~~~~~~

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