oj.uz

Submission #924918

# Submission time Handle Problem Language Result Execution time Memory
924918 2024-02-10T04:31:43 Z HuyQuang_re_Zero Ancient Books (IOI17_books) C++14
100 / 100
 820 ms 259684 KB 
#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],Set[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;
                Set[n_cycle].push_back(j);
            }
           // if(l==2 && r==2) cerr<<p[i]<<'\n';
            seg_cycle[n_cycle]={ l,r };
        }

    sort(seg_cycle+1,seg_cycle+n_cycle+1,[&](II a,II b){ return a.snd<b.snd; });


    //Build extend segment
    FT_mi.Init();
    set <II> vec;
    for(i=1;i<=n_cycle;i++)
    {
        int l=seg_cycle[i].fst,r=seg_cycle[i].snd,x=in[l];
      //  if(l==8 && r==839) cerr<<1<<'\n';
    //    cerr<<l<<" "<<r<<'\n';
   //     if(FT_ma.get(1,l)>=r) continue;
   //     if(l<=s && s<=r) cerr<<l<<" "<<r<<'\n';
        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);
        for(int k:Set[x])
        {
            FT_mi.update(k,l);
            FT_ma.update(k,r);
        }
        vec.insert({ l,r });
    }
   // cerr<<in[8]<<" "<<in[839]<<'\n';
    for(II k:vec)
    {
        int l=k.fst,r=k.snd;
        if(FT_mi.get(l,r)>=l && FT_ma.get(l,r)<=r)
        {
           // cout<<l<<" "<<r<<'\n';
            point[++n_point]={ l,0 };
            point[++n_point]={ r,1 };
        }
    }
 //  cerr<<n_point<<'\n';
    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;
    int mn_len=1e9;
    for(i=1;i<=n_node;i++)
        if(seg_node[i].fst<=s && s<=seg_node[i].snd && mn_len>seg_node[i].snd-seg_node[i].fst)
        {
            mn_len=seg_node[i].snd-seg_node[i].fst;
            pos=i;
        }
    i=pos;
 //   cerr<<seg_node[i].fst<<" "<<seg_node[i].snd<<" "<<p[401]<<'\n';
    while(par[i]>0)
    {
        j=par[i];//cerr<<seg_node[i].fst<<" "<<seg_node[i].snd<<'\n';
        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[a[j][k]].fst-seg_node[a[j][k-1]].snd>1) break;
        }
        for(k=pos;k<a[j].size();k++)
        {
            cr++;
            if(k<a[j].size()-1 && seg_node[a[j][k+1]].fst-seg_node[a[j][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

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

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 65112 KB Output is correct
2 Correct 13 ms 65116 KB Output is correct
3 Correct 13 ms 65112 KB Output is correct
4 Correct 15 ms 65372 KB Output is correct
5 Correct 13 ms 65140 KB Output is correct
6 Correct 13 ms 65116 KB Output is correct
7 Correct 14 ms 65136 KB Output is correct
8 Correct 13 ms 65116 KB Output is correct
9 Correct 13 ms 64972 KB Output is correct
10 Correct 13 ms 65072 KB Output is correct
11 Correct 16 ms 65116 KB Output is correct
12 Correct 13 ms 65132 KB Output is correct
13 Correct 13 ms 65116 KB Output is correct
14 Correct 13 ms 65116 KB Output is correct
15 Correct 14 ms 65116 KB Output is correct
16 Correct 13 ms 65048 KB Output is correct
17 Correct 13 ms 65116 KB Output is correct
18 Correct 14 ms 65116 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 65112 KB Output is correct
2 Correct 13 ms 65116 KB Output is correct
3 Correct 13 ms 65112 KB Output is correct
4 Correct 15 ms 65372 KB Output is correct
5 Correct 13 ms 65140 KB Output is correct
6 Correct 13 ms 65116 KB Output is correct
7 Correct 14 ms 65136 KB Output is correct
8 Correct 13 ms 65116 KB Output is correct
9 Correct 13 ms 64972 KB Output is correct
10 Correct 13 ms 65072 KB Output is correct
11 Correct 16 ms 65116 KB Output is correct
12 Correct 13 ms 65132 KB Output is correct
13 Correct 13 ms 65116 KB Output is correct
14 Correct 13 ms 65116 KB Output is correct
15 Correct 14 ms 65116 KB Output is correct
16 Correct 13 ms 65048 KB Output is correct
17 Correct 13 ms 65116 KB Output is correct
18 Correct 14 ms 65116 KB Output is correct
19 Correct 13 ms 65124 KB Output is correct
20 Correct 14 ms 65104 KB Output is correct
21 Correct 14 ms 65116 KB Output is correct
22 Correct 14 ms 65116 KB Output is correct
23 Correct 13 ms 65116 KB Output is correct
24 Correct 13 ms 65116 KB Output is correct
25 Correct 14 ms 65012 KB Output is correct
26 Correct 14 ms 65020 KB Output is correct
27 Correct 15 ms 65112 KB Output is correct
28 Correct 14 ms 65072 KB Output is correct
29 Correct 14 ms 65116 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 65112 KB Output is correct
2 Correct 13 ms 65116 KB Output is correct
3 Correct 13 ms 65112 KB Output is correct
4 Correct 15 ms 65372 KB Output is correct
5 Correct 13 ms 65140 KB Output is correct
6 Correct 13 ms 65116 KB Output is correct
7 Correct 14 ms 65136 KB Output is correct
8 Correct 13 ms 65116 KB Output is correct
9 Correct 13 ms 64972 KB Output is correct
10 Correct 13 ms 65072 KB Output is correct
11 Correct 16 ms 65116 KB Output is correct
12 Correct 13 ms 65132 KB Output is correct
13 Correct 13 ms 65116 KB Output is correct
14 Correct 13 ms 65116 KB Output is correct
15 Correct 14 ms 65116 KB Output is correct
16 Correct 13 ms 65048 KB Output is correct
17 Correct 13 ms 65116 KB Output is correct
18 Correct 14 ms 65116 KB Output is correct
19 Correct 13 ms 65124 KB Output is correct
20 Correct 14 ms 65104 KB Output is correct
21 Correct 14 ms 65116 KB Output is correct
22 Correct 14 ms 65116 KB Output is correct
23 Correct 13 ms 65116 KB Output is correct
24 Correct 13 ms 65116 KB Output is correct
25 Correct 14 ms 65012 KB Output is correct
26 Correct 14 ms 65020 KB Output is correct
27 Correct 15 ms 65112 KB Output is correct
28 Correct 14 ms 65072 KB Output is correct
29 Correct 14 ms 65116 KB Output is correct
30 Correct 205 ms 96700 KB Output is correct
31 Correct 265 ms 96844 KB Output is correct
32 Correct 504 ms 259592 KB Output is correct
33 Correct 396 ms 215832 KB Output is correct
34 Correct 368 ms 215832 KB Output is correct
35 Correct 337 ms 188348 KB Output is correct
36 Correct 255 ms 136528 KB Output is correct
37 Correct 159 ms 102340 KB Output is correct
38 Correct 144 ms 97860 KB Output is correct
39 Correct 147 ms 97616 KB Output is correct
40 Correct 158 ms 96460 KB Output is correct
41 Correct 178 ms 96516 KB Output is correct
42 Correct 160 ms 96080 KB Output is correct
43 Correct 544 ms 220292 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 65116 KB Output is correct
2 Correct 14 ms 65116 KB Output is correct
3 Correct 14 ms 65116 KB Output is correct
4 Correct 14 ms 65052 KB Output is correct
5 Correct 14 ms 65112 KB Output is correct
6 Correct 13 ms 65120 KB Output is correct
7 Correct 14 ms 65084 KB Output is correct
8 Correct 13 ms 65116 KB Output is correct
9 Correct 14 ms 65240 KB Output is correct
10 Correct 14 ms 65116 KB Output is correct
11 Correct 14 ms 65044 KB Output is correct
12 Correct 13 ms 65112 KB Output is correct
13 Correct 14 ms 65116 KB Output is correct
14 Correct 13 ms 65116 KB Output is correct
15 Correct 13 ms 65116 KB Output is correct
16 Correct 14 ms 65116 KB Output is correct
17 Correct 13 ms 65116 KB Output is correct
18 Correct 13 ms 65116 KB Output is correct
19 Correct 14 ms 65116 KB Output is correct
20 Correct 13 ms 65112 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 65112 KB Output is correct
2 Correct 13 ms 65116 KB Output is correct
3 Correct 13 ms 65112 KB Output is correct
4 Correct 15 ms 65372 KB Output is correct
5 Correct 13 ms 65140 KB Output is correct
6 Correct 13 ms 65116 KB Output is correct
7 Correct 14 ms 65136 KB Output is correct
8 Correct 13 ms 65116 KB Output is correct
9 Correct 13 ms 64972 KB Output is correct
10 Correct 13 ms 65072 KB Output is correct
11 Correct 16 ms 65116 KB Output is correct
12 Correct 13 ms 65132 KB Output is correct
13 Correct 13 ms 65116 KB Output is correct
14 Correct 13 ms 65116 KB Output is correct
15 Correct 14 ms 65116 KB Output is correct
16 Correct 13 ms 65048 KB Output is correct
17 Correct 13 ms 65116 KB Output is correct
18 Correct 14 ms 65116 KB Output is correct
19 Correct 13 ms 65124 KB Output is correct
20 Correct 14 ms 65104 KB Output is correct
21 Correct 14 ms 65116 KB Output is correct
22 Correct 14 ms 65116 KB Output is correct
23 Correct 13 ms 65116 KB Output is correct
24 Correct 13 ms 65116 KB Output is correct
25 Correct 14 ms 65012 KB Output is correct
26 Correct 14 ms 65020 KB Output is correct
27 Correct 15 ms 65112 KB Output is correct
28 Correct 14 ms 65072 KB Output is correct
29 Correct 14 ms 65116 KB Output is correct
30 Correct 205 ms 96700 KB Output is correct
31 Correct 265 ms 96844 KB Output is correct
32 Correct 504 ms 259592 KB Output is correct
33 Correct 396 ms 215832 KB Output is correct
34 Correct 368 ms 215832 KB Output is correct
35 Correct 337 ms 188348 KB Output is correct
36 Correct 255 ms 136528 KB Output is correct
37 Correct 159 ms 102340 KB Output is correct
38 Correct 144 ms 97860 KB Output is correct
39 Correct 147 ms 97616 KB Output is correct
40 Correct 158 ms 96460 KB Output is correct
41 Correct 178 ms 96516 KB Output is correct
42 Correct 160 ms 96080 KB Output is correct
43 Correct 544 ms 220292 KB Output is correct
44 Correct 13 ms 65116 KB Output is correct
45 Correct 14 ms 65116 KB Output is correct
46 Correct 14 ms 65116 KB Output is correct
47 Correct 14 ms 65052 KB Output is correct
48 Correct 14 ms 65112 KB Output is correct
49 Correct 13 ms 65120 KB Output is correct
50 Correct 14 ms 65084 KB Output is correct
51 Correct 13 ms 65116 KB Output is correct
52 Correct 14 ms 65240 KB Output is correct
53 Correct 14 ms 65116 KB Output is correct
54 Correct 14 ms 65044 KB Output is correct
55 Correct 13 ms 65112 KB Output is correct
56 Correct 14 ms 65116 KB Output is correct
57 Correct 13 ms 65116 KB Output is correct
58 Correct 13 ms 65116 KB Output is correct
59 Correct 14 ms 65116 KB Output is correct
60 Correct 13 ms 65116 KB Output is correct
61 Correct 13 ms 65116 KB Output is correct
62 Correct 14 ms 65116 KB Output is correct
63 Correct 13 ms 65112 KB Output is correct
64 Correct 487 ms 213440 KB Output is correct
65 Correct 481 ms 227152 KB Output is correct
66 Correct 160 ms 102344 KB Output is correct
67 Correct 152 ms 101060 KB Output is correct
68 Correct 41 ms 72792 KB Output is correct
69 Correct 33 ms 71400 KB Output is correct
70 Correct 47 ms 75604 KB Output is correct
71 Correct 49 ms 78488 KB Output is correct
72 Correct 66 ms 82512 KB Output is correct
73 Correct 26 ms 68184 KB Output is correct
74 Correct 376 ms 215968 KB Output is correct
75 Correct 375 ms 215896 KB Output is correct
76 Correct 517 ms 218692 KB Output is correct
77 Correct 532 ms 219640 KB Output is correct
78 Correct 444 ms 203080 KB Output is correct
79 Correct 445 ms 203100 KB Output is correct
80 Correct 503 ms 259684 KB Output is correct
81 Correct 664 ms 183416 KB Output is correct
82 Correct 656 ms 183412 KB Output is correct
83 Correct 401 ms 155212 KB Output is correct
84 Correct 325 ms 141584 KB Output is correct
85 Correct 222 ms 117700 KB Output is correct
86 Correct 174 ms 104288 KB Output is correct
87 Correct 820 ms 234888 KB Output is correct
88 Correct 623 ms 211760 KB Output is correct
89 Correct 437 ms 171880 KB Output is correct
90 Correct 159 ms 101456 KB Output is correct
91 Correct 154 ms 97876 KB Output is correct
92 Correct 146 ms 96844 KB Output is correct