Submission #1293788

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293788		_Temirhan	Rabbit Carrot (LMIO19_triusis)	C++20	100 / 100	20 ms	4160 KiB

triusis

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>  
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

#if defined(__GNUC__) || defined(__clang__)
#pragma GCC optimize("Ofast,unroll-loops,inline-functions,no-stack-protector")
#pragma GCC target("avx2,fma,tune=native")
#pragma clang loop vectorize(enable)
#pragma clang loop interleave(enable)
#pragma omp simd
#endif
#ifdef _MSC_VER
#pragma optimize("gt", on)
#pragma loop(ivdep)
#pragma loop(hint_parallel(8))
#pragma loop(hint_unroll, 16)
#pragma float_control(precise, off)
#pragma intrinsic(memcpy, memset)
#pragma fp_contract(on)
#endif

#define int long long
#define sz(x) x.size()
#define F first
#define S second
#define pb push_back
#define nl '\n'
#define o_set tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void Debug()
{
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
}

void file( string s = "" )
{
    if( s.empty() )
        return;
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}

const int N = 2e5 + 2;
const int N1 = 1e6 + 2;
const int inf = 1e9 + 2;
const int INF = 1e18 + 2;
const int mod = 1e9 + 7;
const int MX = 1e9 + 2;
const int dx[4]{0, 1, 0, -1};
const int dy[4]{1, 0, -1, 0};
int T = 1, n, m, a[N];

void solve()
{
    cin >>n >>m;
    for( int i = 1; i <= n; ++i )
        cin >>a[i];
    vector< int >v;
    for( int i = 1; i <= n; ++i )
    {
        if( i * m < a[i] )
            continue;
        a[i] = i * m - a[i];
        int j = upper_bound(v.begin(), v.end(), a[i]) - v.begin();
        if( j == sz(v) )
            v.pb(a[i]);
        else
            v[j] = a[i];
    }
    cout <<n - sz(v);
}

signed main()
{
    // Debug();
    // file("");
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    // cin >>T;
    while( T-- )
        solve();
}

Compilation message (stderr)

triusis.cpp: In function 'void Debug()':
triusis.cpp:37:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         freopen("input.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
triusis.cpp:38:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |         freopen("output.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
triusis.cpp: In function 'void file(std::string)':
triusis.cpp:46:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
triusis.cpp:47:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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