Submission #924778

#	Time	Username	Problem	Language	Result	Execution time	Memory
924778		HuyQuang_re_Zero	Ancient Books (IOI17_books)	C++14	50 / 100	410 ms	148852 KiB

books

#include <bits/stdc++.h>
#define ll long long
#define db long double
#define N 1000005
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define IDB pair <db,int>
#define TII pair <treap*,treap*>
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x)
using namespace std;
#include "books.h"
struct Minimum_Fenwick_Tree
{
    int bit[N],d[N];
    void Init()
    {
        memset(bit,63,sizeof(bit));
        memset(d,63,sizeof(d));
    }
    void update(int i,int k)
    {
        d[i]=min(d[i],k);
        while(i<N) bit[i]=min(bit[i],k),i+=(i & -i);
    }
    int get(int l,int r)
    {
        int res=1e9,i=r;
        while(i>=l)
            if(i-(i & -i)>=l) res=min(res,bit[i]),i-=(i & -i);
            else res=min(res,d[i]),i--;
        return res;
    }
} FT_mi;

struct Maximum_Fenwick_Tree
{
    int bit[N],d[N];
    void update(int i,int k)
    {
        d[i]=max(d[i],k);
        while(i<N) bit[i]=max(bit[i],k),i+=(i & -i);
    }
    int get(int l,int r)
    {
        int res=0,i=r;
        while(i>=l)
            if(i-(i & -i)>=l) res=max(res,bit[i]),i-=(i & -i);
            else res=max(res,d[i]),i--;
        return res;
    }
} FT_ma,FT_done;

int n,i,j,k,pos,p[N],n_cycle,n_node,n_point,in[N],par[N];
vector <int> a[N];
II seg_node[N],seg_cycle[N],point[2*N];
ll minimum_walk(vector <int> _p,int s)
{
    s++;
    for(int k:_p) p[++n]=k,p[n]++;

    //Build cycle
    for(i=1;i<=n;i++)
        if(in[i]==0)
        {
            n_cycle++;
            int l=1e9,r=0;
            for(j=i;in[j]==0;j=p[j])
            {
                l=min(l,j);
                r=max(r,j);
                in[j]=n_cycle;
            }
            seg_cycle[n_cycle]={ l,r };
        }
    FT_mi.Init();
    for(i=1;i<=n;i++)
    {
        FT_mi.update(i,seg_cycle[in[i]].fst);
        FT_ma.update(i,seg_cycle[in[i]].snd);
    }
    sort(seg_cycle+1,seg_cycle+n_cycle+1,[&](II a,II b){ return a.snd<b.snd; });


    //Build extend segment
    for(i=1;i<=n_cycle;i++)
    {
        int l=seg_cycle[i].fst,r=seg_cycle[i].snd;
        if(FT_done.get(1,l)>=r) continue;
        while(1)
        {
            int k;
            if((k=FT_mi.get(l,r))<l) l=k;
            else if((k=FT_ma.get(l,r))>r) r=k;
            else break;
        }
        FT_done.update(l,r);
        point[++n_point]={ l,0 };
        point[++n_point]={ r,1 };
    }
    sort(point+1,point+n_point+1);


    //Build Tree of extend segment
    stack <II> st;
    for(i=1;i<=n_point;i++)
        if(point[i].snd==0) st.push(point[i]);
        else
        {
            n_node++;
            while(st.top().snd==1)
            {
                int u=st.top().fst;
                a[n_node].push_back(u);
                par[u]=n_node;
                st.pop();
            }
            seg_node[n_node]={ st.top().fst,point[i].fst };
            reverse(a[n_node].begin(),a[n_node].end());
            st.pop();
            st.push({ n_node,1 });
        }


    //Init move
    int Begin=0,End=0;
    ll res=0;
    for(i=1;i<=n;i++)
    {
        res+=abs(i-p[i]);
        if(i!=p[i])
        {
            if(Begin==0) Begin=i;
            End=i;
        }
    }
    if(Begin==0) return 0;
    Begin=min(Begin,s);
    End=max(End,s);
    for(i=1;i<=n_node;i++)
    {
        if(seg_node[i].fst>=Begin && seg_node[i].snd<=End && par[i]==0)
        res+=2;
    }
    res-=2;
    for(i=1;i<=n_node;i++)
        if(seg_node[i].fst<=s && s<=seg_node[i].snd && a[i].size()==0)
            break;


    while(par[i]>0)
    {
        j=par[i];
        ll cl=0,cr=0;
        for(pos=0;pos<a[j].size();pos++)
            if(a[j][pos]==i) break;
        for(k=pos;k>=0;k--)
        {
            cl++;
            if(k>0 && seg_node[k].fst-seg_node[k-1].snd>1) break;
        }
        for(k=pos+1;k<a[j].size();j++)
        {
            cr++;
            if(k<a[j].size()-1 && seg_node[k+1].fst-seg_node[k].snd>1) break;
        }
        res+=2*min(cl,cr);
        i=j;
    }
    return res;
}
/*
int main()
{
    freopen("books.inp","r",stdin);
    freopen("books.out","w",stdout);
    vector <int> p;
    int n,s,k;
    cin>>n>>s;
    for(int i=1;i<=n;i++) cin>>k,p.push_back(k);
    cout<<minimum_walk(p,s);
}
*/

Compilation message (stderr)

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:162:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  162 |         for(pos=0;pos<a[j].size();pos++)
      |                   ~~~^~~~~~~~~~~~
books.cpp:169:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  169 |         for(k=pos+1;k<a[j].size();j++)
      |                     ~^~~~~~~~~~~~
books.cpp:172:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  172 |             if(k<a[j].size()-1 && seg_node[k+1].fst-seg_node[k].snd>1) break;
      |                ~^~~~~~~~~~~~~~

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