oj.uz

Submission #678849

# Submission time Handle Problem Language Result Execution time Memory
678849 2023-01-06T17:15:35 Z WebbWayne Studentsko (COCI14_studentsko) C++14
100 / 100
 5 ms 468 KB 
#include <iostream>
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define rep(i, a, b) for(int i = a; i < b; i++)
#define vi vector<int> 
#define ii pair<int, int>
#define pb push_back
#define f first
#define s second
#define all(i) (i).begin(), (i).end()
#define MOD 1000000007
#define endl '\n'

void solve(){
 
	ll n,k;
	cin >> n >> k;
 
	vector<ii> nums(n+1);
	rep(i, 1, n+1) {
		cin>>nums[i].f;
		nums[i].s = i;
	}

	sort(all(nums));

	//Now, we have their actual position with their index.
	vi actual(n+1);
	rep(i, 1, n+1) {
		actual[nums[i].s] = ((i+k-1)/k);
	}

	//Now actual is like 3, 1, 1, 2, 2, 3

	vi sub;
	sub.pb(actual[1]);
	rep(i, 2, n+1) {
		auto itr = upper_bound(sub.begin(), sub.end(), actual[i]);
		if(itr != sub.end()) {
			int ind = itr - sub.begin();
			sub[ind] = actual[i];
		}

		else 
			sub.pb(actual[i]);
	}

	cout<<n - sub.size()<<endl;
}
 
int main(){

 
	ll tc = 1;
	// cin >> tc;
	while(tc--) solve();
 
	return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 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 3 ms 308 KB Output is correct

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

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

Subtask #10
10.0 / 10.0

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