oj.uz

Submission #780759

# Submission time Handle Problem Language Result Execution time Memory
780759 2023-07-12T12:46:11 Z aaron_dcoder Studentsko (COCI14_studentsko) C++17
100 / 100
 3 ms 468 KB 
#define NDEBUG

#ifdef NDEBUG
#define dbg(TXTMSG) (static_cast<int>(0))
#define dbgv(VARN) (static_cast<int>(0))
#else 
#define dbg(TXTMSG) cerr << "\n" << TXTMSG
#define dbgv(VARN) cerr << "\n" << #VARN << " = "<<VARN << ", line: " << __LINE__ << "\n"
#define _GLIBCXX_DEBUG 1
#define _GLIBCXX_DEBUG_PEDANTIC 1
#endif

#include <bits/stdc++.h>
using namespace std;
using ll = long long; 
constexpr ll INFTY = 1e10;
#define var const auto&

int main() {
    ll N,K;
    cin >> N >> K;
    vector<ll> studskill(N);
    vector<pair<ll,ll>> skillist(N);
    for (ll i = 0; i < N; i++)
    {
        cin >> studskill[i];
        skillist[i] = {studskill[i],i};
    }

    sort(skillist.begin(),skillist.end());

    vector<ll> studteam(N,-1);
    for (ll i = 0; i < N; i++)
    {
        studteam[skillist[i].second] = i/K;
    }

    
    vector<ll> lastelem_best_LIS_with_len(N+1,INFTY);
    lastelem_best_LIS_with_len[0] = 0;

    for (ll i = 0; i < N; i++)
    {
        *upper_bound(lastelem_best_LIS_with_len.begin(),lastelem_best_LIS_with_len.end(),studteam[i])
        =studteam[i];
    }

    ll LIS_len = (lower_bound(lastelem_best_LIS_with_len.cbegin(),lastelem_best_LIS_with_len.cend(),INFTY)-lastelem_best_LIS_with_len.cbegin())-1;
    cout << N-LIS_len;
 
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 296 KB Output is correct
2 Correct 0 ms 212 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 444 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 3 ms 444 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 440 KB Output is correct
2 Correct 3 ms 464 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 2 ms 468 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 2 ms 432 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 460 KB Output is correct
2 Correct 2 ms 468 KB Output is correct