Submission #927975

#	Time	Username	Problem	Language	Result	Execution time	Memory
927975		cpptowin	Rabbit Carrot (LMIO19_triusis)	C++17	100 / 100	38 ms	8876 KiB

triusis

#include<bits/stdc++.h>
#define fo(i,d,c) for(int i=d;i<=c;i++)
#define fod(i,c,d) for(int i=c;i>=d;i--)
#define maxn 1000010
#define N 1010
#define fi first
#define se second
#define pb emplace_back
#define en cout<<"\n";
#define int long long
#define inf (int)1e18
#define pii pair<int,int>
#define vii vector<pii>
#define lb(x) x&-x
#define bit(i,j) ((i>>j)&1)
#define offbit(i,j) (i^(1<<j))
#define onbit(i,j) (i|(1<<j))
#define vi vector<int>
template <typename T1, typename T2> bool minimize(T1 &a, T2 b){if (a > b) {a = b; return true;} return false;}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b){if (a < b) {a = b; return true;} return false;}
using namespace std;
const int nsqrt = 450;
const int mod = 1e9 + 7;
int n,m,a[maxn];
struct BIT
{
    int t[maxn];
    void up(int x,int val)
    {
        for( ; x < maxn ; x += lb(x)) t[x] = max(t[x],val);
    }
    int get(int x)
    {
        int ans = 0;
        for( ; x ; x -= lb(x)) ans = max(ans,t[x]);
        return ans;
    }
}t;
vi v;
int ans = 0;
main()
{
    #define name "TASK"
    if(fopen(name".inp","r"))
    {
       freopen(name".inp","r",stdin);
       freopen(name".out","w",stdout);
    }
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    cin >> n >> m;
    v.pb(m);
    fo(i,1,n)
    {
        cin >> a[i];
        if(m * i >= a[i])
        v.pb(m * i - a[i]);
    }
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    fo(i,1,n) if(m * i >= a[i])
    {
        int lb = lower_bound(v.begin(),v.end(),m * i - a[i]) - v.begin() + 1;
        int val = t.get(lb) + 1;
        ans = max(ans,val);
        t.up(lb,val);
    }
    cout << n - ans;
}

Compilation message (stderr)

triusis.cpp:41:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   41 | main()
      | ^~~~
triusis.cpp: In function 'int main()':
triusis.cpp:46:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |        freopen(name".inp","r",stdin);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
triusis.cpp:47:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |        freopen(name".out","w",stdout);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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