Submission #375996

#	Time	Username	Problem	Language	Result	Execution time	Memory
375996		Aldas25	Rabbit Carrot (LMIO19_triusis)	C++14	100 / 100	34 ms	7040 KiB

triusis

#pragma GCC optimize("O3")

#include <bits/stdc++.h>

using namespace std;

#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(nullptr)
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define pb push_back
#define f first
#define s second
typedef long double ld;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<ll> vl;
typedef vector<piii> viii;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MAXN = 500100, MAXK = 23;
const ll MOD = 1e9+7;
const ll INF = 1e16;
const ld PI = asin(1) * 2;

void setIO () {
    FAST_IO;
}

void setIO (string s) {
    setIO();
 	freopen((s+".in").c_str(),"r",stdin);
	freopen((s+".out").c_str(),"w",stdout);
}

int n;
ll m;
ll a[MAXN];
ll b[MAXN];
ll dp[MAXN];

int main() {
	setIO();

    cin >> n >> m;
    FOR(i, 1, n) cin >> a[i];
    FOR(i, 1, n) b[i] = i*m - a[i];

    dp[0] = 0;
    FOR(i,1, n+5) dp[i] = 1e18;

    int k = 0;
    FOR(i,1 , n) {
        if (b[i] < 0) continue;
        //cout <<"  i = " << i << " b = " << b[i] << endl;

        int le = 0, ri = k+1;
        while (le < ri) {
            int mid = (le+ri)/2;
            if (b[i] < dp[mid]) ri = mid;
            else le = mid+1;
        }

        dp[le] = b[i];
        k= max(k, le);

        //cout << "    le  = " << le << endl;

        //FOR(j, 0, n) cout << "   j = " << j << " dp = " << dp[j] << endl;
    }

    int ans = n-k;
    cout << ans << endl;

	return 0;
}

Compilation message (stderr)

triusis.cpp: In function 'void setIO(std::string)':
triusis.cpp:34:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   34 |   freopen((s+".in").c_str(),"r",stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
triusis.cpp:35:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   35 |  freopen((s+".out").c_str(),"w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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