oj.uz

Submission #1118009

# Submission time Handle Problem Language Result Execution time Memory
1118009 2024-11-24T16:51:44 Z dosts Rabbit Carrot (LMIO19_triusis) C++17
0 / 100
 1 ms 336 KB 
//Dost SEFEROĞLU
#include <bits/stdc++.h>
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
using namespace std;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<    
#define all(cont) cont.begin(),cont.end()
#define vi vector<int>

const int inf = 1e18,MOD = 1e9+7;

int add(int x,int y) {
  return ((x+y) >= MOD ? x+y-MOD : x+y);
}
int mult(int x,int y) {
  return ((x*y)%MOD);
}

void solve() {
  int n,m;
  cin >> n >> m;
  vi a(n+1);
  for (int i=1;i<=n;i++) cin >> a[i];
  vi v;
  v.push_back(inf);
  for (int i=1;i<=n;i++) {
      v.push_back(a[i]-m*i);
  }
  vi seq; //longest non-increasing sub
  //2 6 1 5 4 8 3
  //8 5 4 3
  for (int i=0;i<v.size();i++) {
    int l = 1;
    int r = seq.size();
    while (l<=r){
      int m = (l+r) >> 1;
      if (seq[m-1] < v[i]) r = m-1;
      else l = m+1;
    }
    if (l > seq.size()) seq.push_back(v[i]);
    else seq[l-1] = v[i];
  }
  cout << n+1-seq.size() << '\n';
}                    
                             
int32_t main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Dodi
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t; 
    while (t --> 0) solve();
}

Compilation message

triusis.cpp: In function 'void solve()':
triusis.cpp:35:17: 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]
   35 |   for (int i=0;i<v.size();i++) {
      |                ~^~~~~~~~~
triusis.cpp:43:11: 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]
   43 |     if (l > seq.size()) seq.push_back(v[i]);
      |         ~~^~~~~~~~~~~~

Subtask #1
0 / 14.0

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

Subtask #2
0 / 21.0

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

Subtask #3
0 / 28.0

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

Subtask #4
0 / 37.0

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