This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
using namespace std;
typedef int ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll MOD=1e9+7;
const ll MOD2=998244353;
const ll N=1e6+5;
const ll K=350;
const ld pi=acos(-1);
const ll INF=(1LL<<60);
#define SQ(i) ((i)*(i))
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()
ll u[N],n,m,cnt[N],ans[N],dp[N],s[N];
vector<pll> v[2][N];
ll seg[2][4*N];
void ins(ll sid,ll id,ll l,ll r,ll to,ll d){
if(l==r-1){seg[sid][id]+=d;return ;}
ll mid=(l+r)/2;
if(to<mid){
ins(sid,id*2,l,mid,to,d);
}else{
ins(sid,id*2+1,mid,r,to,d);
}
seg[sid][id]=max(seg[sid][id*2],seg[sid][id*2+1]);
}
void add(ll sid,pll A){
if(A.X==A.Y){
v[sid][A.X].pb(A);
}else{
v[sid][A.X].pb(A);
v[sid][A.Y].pb(A);
}
if(A.X)ins(sid,1,1,m+1,A.X,1);
if(A.Y)ins(sid,1,1,m+1,A.Y,1);
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>n>>m;
REP1(i,n){
cin>>u[i];
++cnt[u[i]];
pll tmp=mp(u[i-1],u[i]);
add(i&1,tmp);
if(i==n)add((i+1)&1,mp(u[i],u[i+1]));
}
REP1(i,m){
for(auto j:v[0][i]){
if(j.X)ins(0,1,1,m+1,j.X,-1);
if(j.Y)ins(0,1,1,m+1,j.Y,-1);
}
for(auto j:v[1][i]){
if(j.X)ins(1,1,1,m+1,j.X,-1);
if(j.Y)ins(1,1,1,m+1,j.Y,-1);
}
ans[i]=n-cnt[i]-max(0LL,max(seg[0][1],seg[1][1]));
for(auto j:v[0][i]){
if(j.X)ins(0,1,1,m+1,j.X,1);
if(j.Y)ins(0,1,1,m+1,j.Y,1);
}
for(auto j:v[1][i]){
if(j.X)ins(1,1,1,m+1,j.X,1);
if(j.Y)ins(1,1,1,m+1,j.Y,1);
}
}
REP1(i,m)cout<<ans[i]<<"\n";
return 0;
}
Compilation message (stderr)
rope.cpp:12:18: warning: overflow in conversion from 'long long int' to 'll' {aka 'int'} changes value from '1152921504606846976' to '0' [-Woverflow]
12 | const ll INF=(1LL<<60);
| ~~~~^~~~~
rope.cpp: In function 'int main()':
rope.cpp:70:51: error: no matching function for call to 'max(long long int, const int&)'
70 | ans[i]=n-cnt[i]-max(0LL,max(seg[0][1],seg[1][1]));
| ^
In file included from /usr/include/c++/9/bits/char_traits.h:39,
from /usr/include/c++/9/ios:40,
from /usr/include/c++/9/istream:38,
from /usr/include/c++/9/sstream:38,
from /usr/include/c++/9/complex:45,
from /usr/include/c++/9/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
from rope.cpp:1:
/usr/include/c++/9/bits/stl_algobase.h:222:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
222 | max(const _Tp& __a, const _Tp& __b)
| ^~~
/usr/include/c++/9/bits/stl_algobase.h:222:5: note: template argument deduction/substitution failed:
rope.cpp:70:51: note: deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
70 | ans[i]=n-cnt[i]-max(0LL,max(seg[0][1],seg[1][1]));
| ^
In file included from /usr/include/c++/9/bits/char_traits.h:39,
from /usr/include/c++/9/ios:40,
from /usr/include/c++/9/istream:38,
from /usr/include/c++/9/sstream:38,
from /usr/include/c++/9/complex:45,
from /usr/include/c++/9/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
from rope.cpp:1:
/usr/include/c++/9/bits/stl_algobase.h:268:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
268 | max(const _Tp& __a, const _Tp& __b, _Compare __comp)
| ^~~
/usr/include/c++/9/bits/stl_algobase.h:268:5: note: template argument deduction/substitution failed:
rope.cpp:70:51: note: deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
70 | ans[i]=n-cnt[i]-max(0LL,max(seg[0][1],seg[1][1]));
| ^
In file included from /usr/include/c++/9/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:65,
from rope.cpp:1:
/usr/include/c++/9/bits/stl_algo.h:3456:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
3456 | max(initializer_list<_Tp> __l)
| ^~~
/usr/include/c++/9/bits/stl_algo.h:3456:5: note: template argument deduction/substitution failed:
rope.cpp:70:51: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int'
70 | ans[i]=n-cnt[i]-max(0LL,max(seg[0][1],seg[1][1]));
| ^
In file included from /usr/include/c++/9/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:65,
from rope.cpp:1:
/usr/include/c++/9/bits/stl_algo.h:3462:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
3462 | max(initializer_list<_Tp> __l, _Compare __comp)
| ^~~
/usr/include/c++/9/bits/stl_algo.h:3462:5: note: template argument deduction/substitution failed:
rope.cpp:70:51: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int'
70 | ans[i]=n-cnt[i]-max(0LL,max(seg[0][1],seg[1][1]));
| ^