oj.uz

Submission #1109928

# Submission time Handle Problem Language Result Execution time Memory
1109928 2024-11-08T06:20:15 Z WH8 Studentsko (COCI14_studentsko) C++14
100 / 100
 3 ms 760 KB 
#include <bits/stdc++.h>
using namespace std;
#define iloop(x, n) for (long long i = x; i < n; ++i)
#define jloop(x, n) for (long long j = x; j < n; ++j)
#define kloop(x, n) for (long long k = x; k < n; ++k)
#define dloop(x, n) for (long long d = x; d >= n; --d)
#define ll long long
#define pll pair<long long, long long>
#define pii pair<int, int>
#define iii tuple<int, int, int>
#define vi vector<int>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define int long long
#define endl '\n'
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
#define dg(x) cout << #x << ": " << x << endl
#define all(x) x.begin(), x.end()
#define flag cout << "HERE" << endl;
#define FASTIO               \
    ios::sync_with_stdio(false); \
	cin.tie(0);              \
    cout.tie(0);
#define prt(x) \
    cout << "Vector " << #x << endl << ":"; \
    for (auto it : x) cout << it << " "; \
    cout << endl;
#define ppr(x) \
    cout << "Pair " << #x << endl << ":";\
    cout << x.first << " " << x.second << endl;

int fwt[5005];
int n, k;

void upd(int p, int v){
	while (p <= n){
		fwt[p] = max(fwt[p], v);
		p += (p & (-p));
	}
}

int qrymx(int p){
	int ret = 0;
	while (p){
		ret = max(ret, fwt[p]);
		p -= (p & (-p));
	}
	return ret;
}

int32_t main(){
	FASTIO
	cin >> n >> k;
	vector<int> disc;
	int v[n+1]; iloop(1, n+1){
		int c; cin >> c;
		v[i] = c; 
		disc.pb(c);
	}
	sort(disc.begin(), disc.end());
	disc.erase(unique(disc.begin(), disc.end()), disc.end());
	iloop(1, n+1) v[i] = lower_bound(disc.begin(), disc.end(), v[i]) - disc.begin() + 1;
	iloop(1, n+1){
		if (v[i] % k == 0) v[i] = v[i] / k;
		else v[i] = v[i] / k + 1;
	}
	int longest = 0;
	iloop(1, n+1){
		int mx = qrymx(v[i]);
		longest = max(longest, mx + 1);
		upd(v[i], mx + 1);
	}
	cout << n - longest;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

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

Subtask #10
10.0 / 10.0

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