oj.uz

Submission #997683

# Submission time Handle Problem Language Result Execution time Memory
997683 2024-06-12T17:12:14 Z lucascgar Rabbit Carrot (LMIO19_triusis) C++17
0 / 100
 0 ms 552 KB 
#include <bits/stdc++.h>

// #pragma GCC optimize("Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

using namespace std;

/*
INVERTER PROBLEMA É ÚTIL:
LEAST AMOUNT TO MAKE FIXED:
LARGEST SUBSEQUENCE OF FIXED PILLARS

last fixed i

h[i] + (j-i-1)*M

turn h[i] into reduction to i (have to use double but it works):
i = i - h[i]/m
*/

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); // overclock random

typedef pair<int,int> pii;
typedef pair<long long, long long> pll;
typedef pair<double, double> pdd;

const int MAXN = 2e5+10;

int h[MAXN];

signed main(){
    std::ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    // freopen("test.in", "r", stdin);
    // freopen("test.out", "w", stdout);
    // cout << fixed << setprecision(12);

    int n, m;
    cin >> n >> m;

    if (m == 0){

        int q = 0, x;
        for (int j=0;j<n;j++){
            cin >> x;
            if (x != 0) q++;
        }
        cout << q << "\n";
        return 0;

    }

    vector<double> lis;  // increasing subsequence of positions: lis[i] = last j position of subsequence of size i

    for (int i=1;i<=n;i++){  // try to add you to some sequence if you are fixed
        cin >> h[i];
        if (h[i] > m*i) continue;  // all values must be reachable

        double tg = i - h[i]/m;  // obligatory >=0

        if (lis.empty()){
            lis.push_back(tg);
        }else{

            int p = upper_bound(lis.begin(), lis.end(), tg) - lis.begin();

            if (p == lis.size()) lis.push_back(tg);
            else lis[p] = tg;

        }

    }

    cout << n-lis.size() << "\n";

    return 0;
}

Compilation message

triusis.cpp: In function 'int main()':
triusis.cpp:68:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<double>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |             if (p == lis.size()) lis.push_back(tg);
      |                 ~~^~~~~~~~~~~~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 552 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Incorrect 0 ms 348 KB Output isn't correct
9 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 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 552 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Incorrect 0 ms 348 KB Output isn't correct
9 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 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 552 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Incorrect 0 ms 348 KB Output isn't correct
9 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 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 552 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Incorrect 0 ms 348 KB Output isn't correct
9 Halted 0 ms 0 KB -