Submission #824667

#TimeUsernameProblemLanguageResultExecution timeMemory
824667kshitij_sodaniRope (JOI17_rope)C++17
80 / 100
2569 ms176500 KiB
#include <bits/stdc++.h> #define a first #define b second #define pb push_back using namespace std; #define endl '\n' typedef long long llo; int it[1000001]; int ans[1000001]; int co[1000001]; int vis[1000001]; int vis2[1000001]; vector<int> adj[1000001][2]; int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n,m; cin>>n>>m; for(int i=0;i<m;i++){ ans[i]=n; } for(int i=0;i<n;i++){ cin>>it[i]; it[i]--; co[it[i]]++; ans[it[i]]--; } set<pair<int,int>> xx; for(int i=0;i<m;i++){ xx.insert({co[i],i}); } map<pair<pair<int,int>,int>,int> ss; for(int i=0;i<n-1;i++){ if(it[i]!=it[i+1]){ adj[it[i]][i%2].pb(it[i+1]); adj[it[i+1]][i%2].pb(it[i]); } } for(int i=0;i<m;i++){ vector<int> ss; xx.erase({co[i],i}); ss.pb(i); for(auto j:adj[i][0]){ if(vis[j]==0){ xx.erase({co[j],j}); ss.pb(j); } vis[j]++; } for(auto j:adj[i][1]){ if(vis[j]==0 and vis2[j]==0){ xx.erase({co[j],j}); ss.pb(j); } vis2[j]++; } int cur=co[i]; if(xx.size()){ auto j=xx.end(); j--; ans[i]=min(ans[i],n-cur-(*j).a); } for(auto j:ss){ if(j==i){ continue; } ans[i]=min(ans[i],n-cur-co[j]+min(vis[j],vis2[j])); } for(auto j:ss){ vis[j]=0; vis2[j]=0; } for(auto j:ss){ xx.insert({co[j],j}); } } for(int i=0;i<m;i++){ cout<<ans[i]<<endl; } return 0; }
#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...