Submission #670489

#TimeUsernameProblemLanguageResultExecution timeMemory
670489MahdiRope (JOI17_rope)C++17
100 / 100
1035 ms82936 KiB
#include<bits/stdc++.h> using namespace std; #define all(v) v.begin(), v.end() #define F first #define S second typedef long long ll; typedef pair<int, int> pii; const int N=1e6+5; int n, m, c[N], cnt[N], ans[N]; vector<int>v[N]; bool mk[N]; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin>>n>>m; for(int i=1;i<=n;++i){ cin>>c[i]; v[c[i]].push_back(i); ++cnt[c[i]]; } if(m==1){ cout<<0<<'\n'; return 0; } priority_queue<pii>pq; set<pii>s; for(int i=1;i<=m;++i) pq.push({cnt[i], i}); for(int i=1;i<=m;++i){ vector<int>w, ww; mk[i]=1; for(int u: v[i]){ int z=u+((u&1) ? -1 : 1); if(z>0 && z<=n && c[z]!=i){ z=c[z]; --cnt[z]; mk[z]=1; w.push_back(z); } } while(!pq.empty() && mk[pq.top().S]){ ww.push_back(pq.top().S); pq.pop(); } ans[i]=(pq.empty() ? 0 : pq.top().F); for(int u: w) ans[i]=max(ans[i], cnt[u]); for(int u: w){ ++cnt[u]; mk[u]=0; } mk[i]=0; for(int u: ww) pq.push({cnt[u], u}); } for(int i=1;i<=m;++i){ vector<int>w, ww; mk[i]=1; for(int u: v[i]){ int z=u+((u&1) ? 1 : -1); if(z>0 && z<=n && c[z]!=i){ z=c[z]; --cnt[z]; mk[z]=1; w.push_back(z); } } while(!pq.empty() && mk[pq.top().S]){ ww.push_back(pq.top().S); pq.pop(); } ans[i]=max(ans[i], (pq.empty() ? 0 : pq.top().F)); for(int u: w) ans[i]=max(ans[i], cnt[u]); for(int u: w){ ++cnt[u]; mk[u]=0; } mk[i]=0; for(int u: ww) pq.push({cnt[u], u}); } for(int i=1;i<=m;++i) cout<<n-cnt[i]-ans[i]<<'\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...