Submission #1279248

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279248		MMihalev	Ancient Books (IOI17_books)	C++20	100 / 100	97 ms	27992 KiB

books

#include<iostream>
#include<vector>
//#include "books.h"
using namespace std;
const int MAX_N=1e6+6;
int col[MAX_N];
int cols;
int a[MAX_N];
int l[MAX_N];
int r[MAX_N];
int n;
long long ans;
int b1=1000000000,b2=-1000000000;
pair<int,int>findcomponent(int id)
{
   int ll=id,rr=id;
  int oldl=ll+1,oldr=rr-1;
 
  while(1)
  {
        int nl=ll,nr=rr;
        for(int i=ll;i<min(b1,oldl);i++)
        {
            if(col[i]==0)continue;
            nl=min(nl,l[col[i]]);
            nr=max(nr,r[col[i]]);
        }
        for(int i=max(b2+1,oldr+1);i<=rr;i++)
        {
            if(col[i]==0)continue;
            nl=min(nl,l[col[i]]);
            nr=max(nr,r[col[i]]);
        }
        
        if(nl==ll && nr==rr)break;
        oldl=ll;oldr=rr;
        ll=nl;rr=nr;
  }
  return {ll,rr};
  
}
long long minimum_walk(std::vector<int> p, int s)
{
    n=p.size();
    s++;
    for(int i=1;i<=n;i++)
    {
        l[i]=1e9;
        r[i]=-1;
        a[i]=p[i-1]+1;
    }
    ///init stuff

    for(int i=1;i<=n;i++)
    {
        ans+=abs(i-a[i]);
        if(col[i]==0)
        {
            if(i!=s && i==a[i])continue;
            cols++;
            int pos=i;
            while(col[pos]==0)
            {
                l[cols]=min(l[cols],pos);
                r[cols]=max(r[cols],pos);
                col[pos]=cols;
                pos=a[pos];
            }
        }
    }

    int tmpstart=-1,tmpend=-1;
    int compstart=-1,compend=-1;

    vector<int>sep;
    bool has=0;
    int active=0;
    int e=n;
    while(col[e]==0)e--;
    for(int i=1;i<=e;i++)
    {
        if(has && active==0)
        {
            sep.push_back(i-1);
        }

        int curcol=col[i];
        if(l[curcol]==i)
        {
            if(active==0)tmpstart=i;
            has=1;
            active++;
        }
        if(r[curcol]==i)
        {
            if(active==1)
            {
                tmpend=i;
            }
            active--;
        }

        if(tmpstart<=s && s<=tmpend)
        {
            compstart=tmpstart;
            compend=tmpend;
        }
    }


    int ll=s,rr=s;
    tie(ll,rr)=findcomponent(s);

    while(1)
    {
        if(ll==compstart && rr==compend)break;
        b1=ll;b2=rr;
            int distr=0,tmpr=rr;
            int x=-1,y;
            while(1)
            {
                distr++;
                tmpr++;
                while(col[tmpr]==0)
                {
                    distr++;
                    tmpr++;
                }

                bool foundnew=0;

                int newcomponentl,newcomponentr;
                tie(newcomponentl,newcomponentr)=findcomponent(tmpr);
                if(newcomponentl<ll)
                {
                    x=newcomponentl;
                    y=newcomponentr;
                    foundnew=1;
                }
                else
                {
                    tmpr=newcomponentr;
                }

                if(foundnew)
                {
                   break;
                }
            }
            
            
            int distl=0,tmpl=ll;
            
           
            
            while(1)
            {
              distl++;
              tmpl--;
              while(col[tmpl]==0)
              {
                distl++;
                tmpl--;
              }
              
              bool foundnew=0;
              
                
                
                    int newcomponentl,newcomponentr;
                    tie(newcomponentl,newcomponentr)=findcomponent(tmpl);
                    if(newcomponentr>rr)
                    {
                        ll=newcomponentl;
                        rr=newcomponentr;
                        foundnew=1;
                    }
                    else
                    {
                        tmpl=newcomponentl;
                    }
                if(foundnew)break;
            }
            if(x!=-1){ll=x;rr=y;}
            ans+=2*min(distl,distr);
        
    }



    if(sep.size()==0)return ans;
    ///cycle stuff


    for(int i=sep.size()-1;i>=0;i--)
    {
        if(sep[i]>=s)ans+=2;
    }
    ///right part


    for(int i=0;i<sep.size();i++)
    {
        if(sep[i]<s)ans+=2;
    }
    ///left part


	return ans;
}

• Subtask 1: 12 / 12
• Subtask 2: 10 / 10
• Subtask 3: 28 / 28
• Subtask 4: 20 / 20
• Subtask 5: 30 / 30