oj.uz

Submission #505137

# Submission time Handle Problem Language Result Execution time Memory
505137 2022-01-10T17:18:04 Z trumchepcode Rabbit Carrot (LMIO19_triusis) C++17
0 / 100
 1 ms 332 KB 
#include <bits/stdc++.h>
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]=val;
}
int get(int u)
{
    int ans=0;
    for(int i=u;i>0;i-=i&(-i)) ans=max(ans,bit[i]);
    return ans;
}
int 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

triusis.cpp: In function 'auto nen_so(std::vector<int>)':
triusis.cpp:13:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     for(int i=0;i<v.size();i++) v[i]=mp[v[i]];
      |                 ~^~~~~~~~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Incorrect 0 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Incorrect 0 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Incorrect 0 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Incorrect 0 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -