fork download
copy 
  1. #pragma GCC optimize ("Ofast")
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. void *wmem;
  5. char memarr[96000000];
  6. template<class T> inline void walloc1d(T **arr, int x, void **mem = &wmem){
  7.   static int skip[16] = {0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
  8.   (*mem) = (void*)( ((char*)(*mem)) + skip[((unsigned long long)(*mem)) & 15] );
  9.   (*arr)=(T*)(*mem);
  10.   (*mem)=((*arr)+x);
  11. }
  12. template<class S> inline void arrInsert(const int k, int &sz, S a[], const S aval){
  13.   int i;
  14.   sz++;
  15.   for(i=sz-1;i>k;i--){
  16.     a[i] = a[i-1];
  17.   }
  18.   a[k] = aval;
  19. }
  20. template<class S, class T> inline void arrInsert(const int k, int &sz, S a[], const S aval, T b[], const T bval){
  21.   int i;
  22.   sz++;
  23.   for(i=sz-1;i>k;i--){
  24.     a[i] = a[i-1];
  25.   }
  26.   for(i=sz-1;i>k;i--){
  27.     b[i] = b[i-1];
  28.   }
  29.   a[k] = aval;
  30.   b[k] = bval;
  31. }
  32. template<class S, class T, class U> inline void arrInsert(const int k, int &sz, S a[], const S aval, T b[], const T bval, U c[], const U cval){
  33.   int i;
  34.   sz++;
  35.   for(i=sz-1;i>k;i--){
  36.     a[i] = a[i-1];
  37.   }
  38.   for(i=sz-1;i>k;i--){
  39.     b[i] = b[i-1];
  40.   }
  41.   for(i=sz-1;i>k;i--){
  42.     c[i] = c[i-1];
  43.   }
  44.   a[k] = aval;
  45.   b[k] = bval;
  46.   c[k] = cval;
  47. }
  48. template<class S, class T, class U, class V> inline void arrInsert(const int k, int &sz, S a[], const S aval, T b[], const T bval, U c[], const U cval, V d[], const V dval){
  49.   int i;
  50.   sz++;
  51.   for(i=sz-1;i>k;i--){
  52.     a[i] = a[i-1];
  53.   }
  54.   for(i=sz-1;i>k;i--){
  55.     b[i] = b[i-1];
  56.   }
  57.   for(i=sz-1;i>k;i--){
  58.     c[i] = c[i-1];
  59.   }
  60.   for(i=sz-1;i>k;i--){
  61.     d[i] = d[i-1];
  62.   }
  63.   a[k] = aval;
  64.   b[k] = bval;
  65.   c[k] = cval;
  66.   d[k] = dval;
  67. }
  68. template<class T> int coordcomp_L(int n, T arr[], int res[] = NULL, void *mem = wmem){
  69.   int i;
  70.   int k = 0;
  71.   pair<T,int> *r;
  72.   walloc1d(&r, n, &mem);
  73.   for(i=(0);i<(n);i++){
  74.     r[i].first = arr[i];
  75.     r[i].second = i;
  76.   }
  77.   sort(r, r+n);
  78.   if(res != NULL){
  79.     for(i=(0);i<(n);i++){
  80.       if(i && r[i].first != r[i-1].first){
  81.         k++;
  82.       }
  83.       res[r[i].second] = k;
  84.     }
  85.   }
  86.   else{
  87.     for(i=(0);i<(n);i++){
  88.       if(i && r[i].first != r[i-1].first){
  89.         k++;
  90.       }
  91.       arr[r[i].second] = k;
  92.     }
  93.   }
  94.   return k+1;
  95. }
  96. template <class T> struct DijkstraHeap{
  97.   int *hp;
  98.   int *place;
  99.   int size;
  100.   char *visited;
  101.   T *val;
  102.   void malloc(int N){
  103.     hp = (int*)std::malloc(N*sizeof(int));
  104.     place = (int*)std::malloc(N*sizeof(int));
  105.     visited = (char*)std::malloc(N*sizeof(char));
  106.     val = (T*)std::malloc(N*sizeof(T));
  107.   }
  108.   void free(){
  109.     std::free(hp);
  110.     std::free(place);
  111.     std::free(visited);
  112.     std::free(val);
  113.   }
  114.   void walloc(int N, void **mem=&wmem){
  115.     walloc1d(&hp, N, mem);
  116.     walloc1d(&place, N, mem);
  117.     walloc1d(&visited, N, mem);
  118.     walloc1d(&val, N, mem);
  119.   }
  120.   void init(int N){
  121.     int i;
  122.     size = 0;
  123.     for(i=(0);i<(N);i++){
  124.       place[i]=-1;
  125.     }
  126.     for(i=(0);i<(N);i++){
  127.       visited[i]=0;
  128.     }
  129.   }
  130.   void up(int n){
  131.     int m;
  132.     while(n){
  133.       m=(n-1)/2;
  134.       if(val[hp[m]]<=val[hp[n]]){
  135.         break;
  136.       }
  137.       swap(hp[m],hp[n]);
  138.       swap(place[hp[m]],place[hp[n]]);
  139.       n=m;
  140.     }
  141.   }
  142.   void down(int n){
  143.     int m;
  144.     for(;;){
  145.       m=2*n+1;
  146.       if(m>=size){
  147.         break;
  148.       }
  149.       if(m+1<size&&val[hp[m]]>val[hp[m+1]]){
  150.         m++;
  151.       }
  152.       if(val[hp[m]]>=val[hp[n]]){
  153.         break;
  154.       }
  155.       swap(hp[m],hp[n]);
  156.       swap(place[hp[m]],place[hp[n]]);
  157.       n=m;
  158.     }
  159.   }
  160.   void change(int n, T v){
  161.     if(visited[n]||(place[n]>=0&&val[n]<=v)){
  162.       return;
  163.     }
  164.     val[n]=v;
  165.     if(place[n]==-1){
  166.       place[n]=size;
  167.       hp[size++]=n;
  168.       up(place[n]);
  169.     }
  170.     else{
  171.       up(place[n]);
  172.     }
  173.   }
  174.   int pop(void){
  175.     int res=hp[0];
  176.     place[res]=-1;
  177.     size--;
  178.     if(size){
  179.       hp[0]=hp[size];
  180.       place[hp[0]]=0;
  181.       down(0);
  182.     }
  183.     visited[res]=1;
  184.     return res;
  185.   }
  186. }
  187. ;
  188. struct graph{
  189.   int N;
  190.   int *es;
  191.   int **edge;
  192.   void setDirectEdge(int N__, int M, int A[], int B[], void **mem = &wmem){
  193.     int i;
  194.     N = N__;
  195.     walloc1d(&es, N, mem);
  196.     walloc1d(&edge, N, mem);
  197.     walloc1d(&edge[0], M, mem);
  198.     for(i=(0);i<(N);i++){
  199.       es[i] = 0;
  200.     }
  201.     for(i=(0);i<(M);i++){
  202.       es[A[i]]++;
  203.     }
  204.     for(i=(0);i<(N);i++){
  205.       walloc1d(&edge[i], es[i], mem);
  206.     }
  207.     for(i=(0);i<(N);i++){
  208.       es[i] = 0;
  209.     }
  210.     for(i=(0);i<(M);i++){
  211.       edge[A[i]][es[A[i]]++] = B[i];
  212.     }
  213.   }
  214.   void getDist(int root, int res[], void *mem = wmem){
  215.     int i;
  216.     int j;
  217.     int k;
  218.     int*q;
  219.     int s;
  220.     int z;
  221.     walloc1d(&q, N, &mem);
  222.     for(i=(0);i<(N);i++){
  223.       res[i]=-1;
  224.     }
  225.     res[root]=0;
  226.     s=0;
  227.     z=1;
  228.     q[0]=root;
  229.     while(z){
  230.       i=q[s++];
  231.       z--;
  232.       for(j=(0);j<(es[i]);j++){
  233.         k=edge[i][j];
  234.         if(res[k]>=0){
  235.           continue;
  236.         }
  237.         res[k]=res[i]+1;
  238.         q[s+z++]=k;
  239.       }
  240.     }
  241.   }
  242. }
  243. ;
  244. template<class T> struct wgraph{
  245.   int N;
  246.   int *es;
  247.   int **edge;
  248.   T **cost;
  249.   graph g;
  250.   void setDirectEdge(int N__, int M, int A[], int B[], T C[], void **mem = &wmem){
  251.     int i;
  252.     N = N__;
  253.     walloc1d(&es, N, mem);
  254.     for(i=(0);i<(N);i++){
  255.       es[i] = 0;
  256.     }
  257.     for(i=(0);i<(M);i++){
  258.       es[A[i]]++;
  259.     }
  260.     walloc1d(&edge, N, mem);
  261.     for(i=(0);i<(N);i++){
  262.       walloc1d(&edge[i], es[i], mem);
  263.     }
  264.     walloc1d(&cost, N, mem);
  265.     for(i=(0);i<(N);i++){
  266.       walloc1d(&cost[i], es[i], mem);
  267.     }
  268.     for(i=(0);i<(N);i++){
  269.       es[i] = 0;
  270.     }
  271.     for(i=(0);i<(M);i++){
  272.       edge[A[i]][es[A[i]]] = B[i];
  273.       cost[A[i]][es[A[i]]++] = C[i];
  274.     }
  275.     g.N = N;
  276.     g.es = es;
  277.     g.edge = edge;
  278.   }
  279.   template<class S> void getDist(int root, S res[], S unreachable = -1, void *mem = wmem){
  280.     int i;
  281.     int j;
  282.     DijkstraHeap<S> hp;
  283.     hp.walloc(N, &mem);
  284.     hp.init(N);
  285.     hp.change(root,0);
  286.     while(hp.size){
  287.       i = hp.pop();
  288.       for(j=(0);j<(es[i]);j++){
  289.         hp.change(edge[i][j], hp.val[i]+cost[i][j]);
  290.       }
  291.     }
  292.     for(i=(0);i<(N);i++){
  293.       res[i] = (hp.visited[i] ? hp.val[i] : unreachable);
  294.     }
  295.   }
  296. }
  297. ;
  298. #define main dummy_main
  299. int main(){
  300.   wmem = memarr;
  301.   return 0;
  302. }
  303. #undef main
  304. int N;
  305. int A[100000];
  306. int sz;
  307. int n;
  308. int m;
  309. int a[600000];
  310. int b[600000];
  311. int c[600000];
  312. int d[200000];
  313. wgraph<int> g;
  314. class Solution{
  315.   public:
  316.   int minJumps(vector<int>& arr){
  317.     int i;
  318.     dummy_main();
  319.     N = arr.size();
  320.     for(i=(0);i<(N);i++){
  321.       A[i] = arr[i];
  322.     }
  323.     sz =coordcomp_L(N, A);
  324.     n = N + sz;
  325.     m = 0;
  326.     for(i=(1);i<(N);i++){
  327.       arrInsert(m,m,a,i,b,i-1,c,1);
  328.     }
  329.     for(i=(1);i<(N);i++){
  330.       arrInsert(m,m,a,i-1,b,i,c,1);
  331.     }
  332.     for(i=(0);i<(N);i++){
  333.       arrInsert(m,m,a,i,b,N+A[i],c,1);
  334.       arrInsert(m,m,a,N+A[i],b,i,c,0);
  335.     }
  336.     g.setDirectEdge(n,m,a,b,c);
  337.     g.getDist(0,d);
  338.     return d[N-1];
  339.   }
  340. }
  341. ;
  342. // cLay varsion 20200214-1
  343.  
  344. // --- original code ---
  345. // #define main dummy_main
  346. // {}
  347. // #undef main
  348. // 
  349. // int N, A[1d5];
  350. // int sz, n, m, a[6d5], b[6d5], c[6d5], d[2d5];
  351. // wgraph<int> g;
  352. // 
  353. // class Solution {
  354. // public:
  355. //   int minJumps(vector<int>& arr) {
  356. //     dummy_main();
  357. //     N = arr.size();
  358. //     rep(i,N) A[i] = arr[i];
  359. //     sz = coordcomp(N, A);
  360. //     n = N + sz;
  361. //     m = 0;
  362. //     rep(i,1,N) arrInsert(m,m,a,i,b,i-1,c,1);
  363. //     rep(i,1,N) arrInsert(m,m,a,i-1,b,i,c,1);
  364. //     rep(i,N){
  365. //       arrInsert(m,m,a,i,b,N+A[i],c,1);
  366. //       arrInsert(m,m,a,N+A[i],b,i,c,0);
  367. //     }
  368. // 
  369. //     g.setDirectEdge(n,m,a,b,c);
  370. //     g.getDist(0,d);
  371. //     return d[N-1];
  372. //   }
  373. // };
  374.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
/usr/bin/ld: /usr/lib/gcc/x86_64-linux-gnu/8/../../../x86_64-linux-gnu/Scrt1.o: in function `_start':
(.text+0x20): undefined reference to `main'
collect2: error: ld returned 1 exit status
stdout
copy 
Standard output is empty
https://ideone.com/d71M6R
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!