oj.uz

Submission #1011528

# Submission time Handle Problem Language Result Execution time Memory
1011528 2024-06-30T14:58:27 Z handlename Rabbit Carrot (LMIO19_triusis) C++17
0 / 100
 0 ms 348 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define float long double
const int MOD=1e9+7;
// const int MOD=998244353;
const int sqn=450;
const long double eps=1e-6;
const int dx[4]={0,0,1,-1};
const int dy[4]={1,-1,0,0};
long long power(long long a,long long b,long long p=MOD){
    long long res=1;
    while (b>0){
        if (b%2==1) res=(res*a)%p;
        b/=2;
        a=(a*a)%p;
    }
    return res;
}
long long n,m,arr[200001];
void runtc(){
    cin>>n>>m;
    for (int i=0;i<n;i++){
        cin>>arr[i];
        //if 2 poles dont change,
        //arr[j]-arr[i]<=m*(j-i)
        //m*i-arr[i]<=m*j-arr[j]
        arr[i]=m*i-arr[i];
    }
    //we maximise number of poles we dont change
    vector<int> ans;
    for (int i=0;i<n;i++){
        int pos=upper_bound(ans.begin(),ans.end(),arr[i])-ans.begin();
        if (pos==ans.size()) ans.pb(arr[i]);
        else {
            ans[pos]=arr[i];
        }
    }
    cout<<n-ans.size();
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // freopen("pcb.in","r",stdin);
    // freopen("pcb.out","w",stdout);
    // freopen("input1.in","r",stdin);
    // freopen("output1.out","w",stdout);
    //freopen("tower_rush_input.txt","r",stdin);
    //freopen("hackercup_output.txt","w",stdout);
    int tcs;
    // cin>>tcs;
    tcs=1;
    for (int i=1;i<=tcs;i++){
        // cout<<"Case #"<<i<<": ";
        runtc();
    }
}

Compilation message

triusis.cpp: In function 'void runtc()':
triusis.cpp:35:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |         if (pos==ans.size()) ans.pb(arr[i]);
      |             ~~~^~~~~~~~~~~~

Subtask #1
0 / 14.0

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

Subtask #2
0 / 21.0

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

Subtask #3
0 / 28.0

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

Subtask #4
0 / 37.0

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