Submission #1226720

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226720		dibamboo23	학생 (COCI14_studentsko)	C++20	100 / 100	1 ms	584 KiB

studentsko

#include <bits/stdc++.h>

#define ll long long
#define F first
#define S second
#define sz size()

using namespace std;

[[maybe_unused]]const int e6=1e6;
[[maybe_unused]]const int e7=1e7;
[[maybe_unused]]const int e8=1e8;
[[maybe_unused]]const int e9=1e9;

inline int rd(){
	int num;cin>>num;
	return num;
}

inline ll rdll(){
	ll num;cin>>num;
	return num;
}

[[maybe_unused]]const ll inf=1e18+7;
[[maybe_unused]]const ll MOD=1e9+7;
[[maybe_unused]]const int N=1e6+3;

int a[N];
int bl[N];

void code(){
	int n,k;cin>>n>>k;
	vector<pair<int,int>>v;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		v.push_back({a[i],i});
	}
	sort(v.begin(),v.end());
	for(int i=0;i<(int)v.sz;i++)bl[v[i].S]=i/k;
	vector<int>b={bl[1]};
	for(int i=2;i<=n;i++){
		if(b.back()<=bl[i])b.push_back(bl[i]);
		else{
			auto it=upper_bound(b.begin(),b.end(),bl[i]);
			if(it==b.end())continue;
			*it=bl[i];
		}
	}
	cout<<n-(int)b.sz;
}




signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int tt=1;
	// cin>>tt;
	while(tt--)code(),cout<<"\n";
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10