1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include <cstdio>
#include "krazki.h"
#include "message.h"

#define instanceh 16777216
//#define instanceh 4


int n,m;

/*
long long tab1[1000],tab2[1000];
void init(){
     scanf("%lld%lld",&n,&m);
     int i;
     for(i=0;i<n;i++)
          scanf("%lld",&tab1[i]);
     for(i=0;i<m;i++)
          scanf("%lld",&tab2[i]);                     
}

long long PipeHeight(){
     return n;
}
long long NumberOfDiscs(){
     return m;
}
long long HoleDiameter(long long h){
     return tab1[h-1];
}
long long DiscDiameter(long long d){
     return tab2[d-1];
}
*/


int i,j,k;
long long min;
long long temp,temp1;
long long diams[512];
long long actInstance[instanceh];
int firstIndex;
int restProblems;
int tabIndex;
int height;
int n_index;


int readNewTab(){
    n_index = ((height-1)/instanceh)-1;
    if(n_index<0){
         min=1000000000000000001LL;
         for(k=1;k<=firstIndex;k++){
              temp1=HoleDiameter(k);
              min = min < temp1 ? min : temp1;   
              actInstance[k-1]=min;
         }
         tabIndex=firstIndex-1;
    }
    else{
         if(diams[n_index]<temp){
              height-=instanceh;
              readNewTab();
         }
         else{
             for(k=1;k<=instanceh;k++){
                  min=diams[n_index];
                  temp1=HoleDiameter(firstIndex+k+(instanceh*n_index));
                  min = min < temp1 ? min : temp1;   
                  actInstance[k-1]=min;
             }
             tabIndex=instanceh-1;
         }
    }
    return 0;
}

int main(){
  //  init();
  if (MyNodeId() > 0)
  	return 0;
    n = PipeHeight();
    m = NumberOfDiscs();
    min=1000000000000000001LL;
    firstIndex = n%instanceh;
    restProblems = n/instanceh;
    if(firstIndex==0){
         firstIndex+=instanceh;
         restProblems-=1;          
    }
    // policz skroty
    for(i=1;i<=firstIndex;i++){
         temp = HoleDiameter(i);         
         min = min < temp ? min : temp;    
         actInstance[i-1]=min;                              
    }
    tabIndex=firstIndex-1;
    for(j=0;j<restProblems;j++){
         diams[j]=min;
         for(i=1;i<=instanceh;i++){
              temp = HoleDiameter(firstIndex+j*instanceh+i);   
              min = min < temp ? min : temp;   
              actInstance[i-1]=min;      
         }  
         tabIndex=instanceh-1;
         n_index = 1;                          
    }
    /////////////////////////// wrzucaj krazki
    height = n;   
    for(i=1;i<=m;i++){
         temp = DiscDiameter(i);
         while(actInstance[tabIndex] < temp){
              tabIndex--;
              if(!--height){
                   height=-1;
                   goto label;
              }
              if(tabIndex==-1){//czytaj nowa tabele
                   readNewTab();
              }
         }  
         tabIndex--;
         if(!--height){
              if(i<m)height=-1;
              break;
         }
         if(tabIndex==-1){ //czytaj nowa tabele
                   readNewTab();
         }
    }
    label:
    printf("%d",height+1);
      
}