#include <bits/stdc++.h>
#define MAXN 201010
#define INF 987654321
using namespace std;
struct dat{
int w,cnt;
bool operator<(const dat &r)const{
if(w!=r.w)return w<r.w;
return cnt<r.cnt;
}
}tree[MAXN<<2];
int lazy[MAXN<<2];
dat dp[MAXN];
vector<int>v[MAXN];
int a[MAXN],pre[MAXN],n,k;
long long int ans;
void prop(int no,int ns,int ne){
if(ns!=ne){
lazy[no<<1]+=lazy[no];
lazy[no<<1|1]+=lazy[no];
}
tree[no].w+=lazy[no];
lazy[no]=0;
}
void update1(int no,int ns,int ne,int an,dat val){
if(an>ne || an<ns)return;
if(ns==ne){
tree[no]=val;
return;
}
int mid=ns+ne>>1;
update1(no<<1,ns,mid,an,val);
update1(no<<1|1,mid+1,ne,an,val);
tree[no]=max(tree[no<<1],tree[no<<1|1]);
}
void update2(int no,int ns,int ne,int as,int ae,int val){
prop(no,ns,ne);
if(as>ne || ns>ae)return;
if(as<=ns && ne<=ae){
lazy[no]+=val;
prop(no,ns,ne);
return;
}
int mid=ns+ne>>1;
update2(no<<1,ns,mid,as,ae,val);
update2(no<<1|1,mid+1,ne,as,ae,val);
tree[no]=max(tree[no<<1],tree[no<<1|1]);
}
dat aliens(int c){
for(int i=1 ; i<=n*4; i++)tree[i]={-INF,0};
memset(lazy,0,sizeof(lazy));
for(int i=1 ; i<=n ; i++){
update1(1,1,n,i,dp[i-1]);
update2(1,1,n,pre[i]+1,i,1);
dp[i]={tree[1].w-c,tree[1].cnt+1};
}
return dp[n];
}
void bsearch(int low,int high){
if(high<low)return;
int mid=low+high>>1;
dat x=aliens(mid);
ans=min(ans,(long long int)x.w+(long long int)k*(long long int)mid);
if(x.cnt<=k)bsearch(low,mid-1);
else bsearch(mid+1,high);
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
cin >> n >> k;
for(int i=1 ; i<=n ; i++){
cin>>a[i];
v[a[i]].push_back(i);
}
for(int i=1 ; i<=n ; i++){
for(int j=0 ; j<v[i].size() ; j++){
if(j!=0)pre[v[i][j]]=v[i][j-1];
else pre[v[i][j]]=0;
}
}
ans=n;
bsearch(0,n);
cout<<(int)ans<<"\n";
return 0;
}
Compilation message
sequence.cpp: In function 'void update1(int, int, int, int, dat)':
sequence.cpp:32:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
32 | int mid=ns+ne>>1;
| ~~^~~
sequence.cpp: In function 'void update2(int, int, int, int, int, int)':
sequence.cpp:46:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
46 | int mid=ns+ne>>1;
| ~~^~~
sequence.cpp: In function 'void bsearch(int, int)':
sequence.cpp:65:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
65 | int mid=low+high>>1;
| ~~~^~~~~
sequence.cpp: In function 'int main()':
sequence.cpp:84:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | for(int j=0 ; j<v[i].size() ; j++){
| ~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
4 ms |
8148 KB |
Unexpected end of file - int32 expected |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
5 ms |
8148 KB |
Unexpected end of file - int32 expected |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
5 ms |
8148 KB |
Unexpected end of file - int32 expected |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
9 ms |
8276 KB |
Unexpected end of file - int32 expected |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
55 ms |
8692 KB |
Unexpected end of file - int32 expected |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
786 ms |
13548 KB |
Unexpected end of file - int32 expected |
2 |
Halted |
0 ms |
0 KB |
- |