| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 165646 | Segtree | 고대 책들 (IOI17_books) | C++14 | 0 ms | 0 KiB |
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<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<unordered_set>
#include<set>
#include"books.h"
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<int> vi;
#define N 1000010
namespace uf{
ll par[N];
void init(){
for(int i=0;i<N;i++)par[i]=i;
}
ll pare(ll x){
return par[x]=(par[x]==x?x:pare(par[x]));
}
void unite(ll a,ll b){
a=pare(a),b=pare(b);
par[a]=b;
}
};
vector<int> cyc[N];
struct qry{
ll l,r,id;
bool type;
bool operator<(const qry&key)const{
return this->l<key.l;
}
qry(ll l,ll r,ll id,bool type){
this->l=l,this->r=r,this->id=id,this->type=type;
}
};
int wh[N];
vector<P> g[N];
void makee(ll a,ll b,ll c){
//cout<<"edge:"<<a<<" "<<b<<" "<<c<<endl;
g[a].push_back(make_pair(b,c));
}
ll dist[N];
ll minimum_walk(vi p,int s){
int n=p.size();
ll ans=0;
int m=0;
unordered_set<int> vis;
for(int i=0;i<n;i++){
if(vis.find(i)!=vis.end())continue;
ll x=i;
while(1){
vis.insert(x);
cyc[m].push_back(x);
ans+=abs(x-p[x]);
x=p[x];
if(x==i)break;
}
if(cyc[m].size()==1)cyc[m].clear();
else{
sort(cyc[m].begin(),cyc[m].end());
m++;
}
}/*
cout<<"H"<<endl;
cout<<m<<endl;
for(int i=0;i<m;i++){
for(auto t:cyc[i])cout<<t<<" "; cout<<endl;
}*/
uf::init();
vector<qry> Q;
for(int i=0;i<m;i++){
for(int j=1;j<cyc[i].size();j++){
Q.push_back(qry(cyc[i][0],cyc[i][j],i,0));
}
for(int j=0;j<cyc[i].size()-1;j++){
Q.push_back(qry(cyc[i][j],cyc[i].back(),i,1));
}
}
sort(Q.begin(),Q.end());
priority_queue<P,vector<P>,greater<P> > S;
for(auto t:Q){
if(t.type==0){
S.push(make_pair(t.r,t.id));
}
if(t.type==1){
P last=make_pair(-1,-1);
while(!S.empty()&&S.top().first<t.r){
uf::unite(S.top().second,t.id);
last=S.top();
S.pop();
}
if(last.first!=-1){
S.push(last);
}
}
}
for(int i=0;i<n;i++)wh[i]=-1;
for(int i=0;i<m;i++){
int pp=uf::pare(i);
if(i!=pp){
for(auto t:cyc[i]){
cyc[pp].push_back(t);
wh[t]=pp;
}
cyc[i].clear();
}
else{
for(auto t:cyc[i])wh[t]=i;
}
}/*
cout<<"He"<<endl;
for(int i=0;i<m;i++){
for(auto t:cyc[i])cout<<t<<" "; cout<<endl;
}*/
vector<ll> kyma;
Q.clear(); //Q reuse
for(int i=0;i<m;i++){
if(cyc[i].size()==0)continue;
Q.push_back(qry(cyc[i][0],cyc[i].back(),i,0));
}
sort(Q.begin(),Q.end());
stack<int> st;
int nxtl=-1;
for(auto t:Q){
while(!st.empty()&&cyc[st.top()].back()<t.l){
nxtl=st.top();
st.pop();
}
if(~nxtl){
ll cost=t.l-cyc[nxtl].back();
makee(nxtl,t.id,cost);
makee(t.id,nxtl,cost);
}
if(!st.empty()){
auto it=lower_bound(cyc[st.top()].begin(),cyc[st.top()].end(),t.l);
ll rs=*it;
it--; ll ls=*it;
ll cost=2*min(t.l-ls,rs-t.r);
makee(t.id,st.top(),cost);
}
else{
kyma.push_back(t.id);
}
}
//cout<<"Li"<<endl;
for(int i=0;i<n;i++){
if(~wh[i])makee(m,wh[i],2*abs(s-i));
}
for(int i=0;i<=m;i++)dist[i]=1e17;
while(!S.empty())S.pop(); //S.reuse
S.push(make_pair(0,m));
while(!S.empty()){
ll cost=S.top().first;
ll x=S.top().second;
S.pop();
if(dist[x]<=cost)continue;
dist[x]=cost;
for(auto y:g[x]){
S.push(make_pair(cost+y.second,y.first));
}
}
//for(int i=0;i<=m;i++)cout<<dist[i]<<" ";cout<<endl;
ll mi=1e17;
for(auto t:kyma){
chmin(mi,dist[t]);
}
ans+=mi;
for(int i=0;i<kyma.size()-1;i++){
ans+=2*(cyc[kyma[i+1]].l-cyc[kyma[i]]);
}
return ans;
}/*
int main(){
int n,s; cin>>n>>s;
vi p(n);
for(int i=0;i<n;i++){
cin>>p[i];
}
cout<<minimum_walk(p,s)<<endl;
}*/