Submission #505139

#	Time	Username	Problem	Language	Result	Execution time	Memory
505139		trumchepcode	Rabbit Carrot (LMIO19_triusis)	C++14	100 / 100	131 ms	29632 KiB

triusis

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+1;
int  a[N],n,m;
vector<int> v;
auto nen_so(vector<int>v)
{
    set<int>st;
    for(int x:v) st.insert(x);
    map<int,int>mp;
    int cnt=1;
    for(auto x:st) mp[x]=cnt++;
    for(int i=0;i<v.size();i++) v[i]=mp[v[i]];
    return v;
}
int bit[N];
void update(int u,int val)
{
    for(int i=u;i<=N;i+=i&(-i)) bit[i]=max(val,bit[i]);
}
int get(int u)
{
    int ans=0;
    for(int i=u;i>0;i-=i&(-i)) ans=max(ans,bit[i]);
    return ans;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
  //  freopen("test.inp","r",stdin);
  // freopen("test.out","w",stdout);
    cin >> n >> m;
    for(int i=1; i<=n; i++)
    {
        cin >> a[i];
        a[i]=m*i-a[i];
    }
    for(int i=1;i<=n;i++)
    {
        if(a[i]>=0) v.push_back(a[i]);
    }
   auto ds=nen_so(v);
   for(int x:ds)
   {
        update(x,get(x)+1);
   }
   cout << n-get(n);
}

Compilation message (stderr)

triusis.cpp: In function 'auto nen_so(std::vector<long long int>)':
triusis.cpp:14:18: 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]
   14 |     for(int i=0;i<v.size();i++) v[i]=mp[v[i]];
      |                 ~^~~~~~~~~

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