Submission #575213

#	Time	Username	Problem	Language	Result	Execution time	Memory
575213		Bad_day_toCode	Rabbit Carrot (LMIO19_triusis)	C++17	100 / 100	32 ms	6988 KiB

triusis

#include <bits/stdc++.h>

using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

typedef tree<
    int,
    null_type,
    less_equal<int>,
    rb_tree_tag,
    tree_order_statistics_node_update>
    ordered_set;

#define ll long long int
#define fo(i, n) for (ll i = 0; i < n; i++)
#define Fo(i, k, n) for (ll i = k; i < n; i++)
#define fvr(it, v) for (auto it = v.rbegin(); it != v.rend(); ++it)
#define ALL(c) (c).begin(), (c).end() // handy for function like "sort()"
#define mod 1000000007
#define ff first
#define ss second
const long long MOD = 998244353;
const long long INF = 1e9 + 7;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vli;
typedef pair<int, int> pii;
long long sq(int x) { return 1ll * x * x; }
const int MAXN = 10001;

// Sieve
ll d[MAXN], divCnt[MAXN];
vector<ll> primes;
void sieve(ll n)
{

    fo(i, n)
    {
        d[i] = i;
    }
    Fo(i, 2, n)
    {
        if (d[i] == i)
            primes.push_back(i);

        for (ll j = 0; j < ((ll)primes.size()) && primes[j] <= d[i] && primes[j] * i < n; j++)
        {
            d[i * primes[j]] = primes[j];
        }
    }
    Fo(i, 2, n)
    {
        ll j = i / d[i];
        divCnt[n] = divCnt[j] + (d[i] != d[j]);
    }
}
// ll primeFactors(ll n)
// {
//     set<ll> factors;
//     while (n != 1)
//     {
//         factors.insert(d[n]);
//         n /= d[n];
//     }
//     return factors.size();
// }
ll mul(ll x, ll y)
{
    return (x * 1ll * y) % MOD;
}

ll binpow(ll a, ll b, ll c)

{
    ll res = 1;
    a = a % c;
    while (b > 0)
    {
        if (b & 1)
            res = (res * a) % c;

        b = b >> 1;
        a = (a * a) % c;
    }
    return res;
}
long long gcd(long long int a, long long int b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

// int fact[200043];

// void precalc()
// {
//     fact[0] = 1;
//     for (int i = 1; i < 200043; i++)
//         fact[i] = mul(fact[i - 1], i);
// }

// Function to return LCM of two numbers
// int lcm(int a, int b)
// {
//     return (a / gcd(a, b)) * b;
// }
ll inv(ll x, ll c)
{
    return binpow(x, c - 2, c);
}

// int divide(int x, int y, int c)
// {
//     return mul(x, inv(y, c));
// }
// int nCr(int n, int r, int c)
// {
//     return divide(fact[n], mul(fact[r], fact[n - r]), c);
// }
bool cmp1(const pair<ll, ll> &a, const pair<ll, ll> &b)
{
    if (a.first == b.first)
    {
        return a.second < b.second;
    }
    return a.first > b.first;
}
bool cmp2(const pair<ll, ll> &a, const pair<ll, ll> &b)
{
    if (a.second == b.second)
    {
        return a.first < b.first;
    }
    return a.second > b.second;
}
ll find_sum(ll idx, vector<ll> &bit)
{
    ll ans = 0;
    for (; idx > 0; idx -= idx & (-idx))
        ans += bit[idx];
    return ans;
}
void update(ll pos, ll val, vector<ll> &bit)
{
    for (; pos <= bit.size(); pos += pos & (-pos))
    {
        bit[pos] += val;
    }
}

ll longInc(vector<ll>& a){
    ll n=a.size();
    vector<ll> dp(n+1);
    fo(i,n+1)dp[i]=INF;
    dp[0]=0;
    fo(i,n){
        ll p=upper_bound(ALL(dp),a[i])-dp.begin();
        p-=1;
       
        if(dp[p]<=a[i]){
            dp[p+1]=min(dp[p+1],a[i]);
        }
       
    }
    ll idx=0;
    Fo(i,1,n+1){
        if(dp[i]!=INF)idx=i;
    }
    return idx;

}
void solve()
{

    ll n,m;
    cin>>n>>m;
    vector<ll> s(n);
    vector<ll> a;
   
    fo(i,n){
        cin>>s[i];
        if((i+1)*m-s[i]>=0){
            a.push_back((i+1)*m-s[i]);
            
        }
    }
    cout<<n-longInc(a);
  
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t, i = 0;
    t = 1;
    // freopen("cowjog.in", "r", stdin);

    // freopen("cowjog.out", "w", stdout);
    // cin >> t;

    while (t--)
    {
        i++;
        // cout<<"Case #"<<i<<": ";
        solve();
    }
}

Compilation message (stderr)

triusis.cpp: In function 'void update(long long int, long long int, std::vector<long long int>&)':
triusis.cpp:148:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  148 |     for (; pos <= bit.size(); pos += pos & (-pos))
      |            ~~~~^~~~~~~~~~~~~

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