Guest User

Untitled

a guest
Jun 2nd, 2018
180
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.38 KB | None | 0 0
  1. #include <bits/stdc++.h>   //72%. Supera i limiti di memoria
  2.  
  3. //#include "grader.cpp"
  4. using namespace std;
  5.  
  6. //vector <int> V;
  7. //vector <vector <int> > sparse_table;
  8. int V[1000001];
  9. int sparse_table[1000001][20];
  10.  
  11.  
  12.  
  13.  
  14. int RMQ (int a, int b) {  //range MAXIMUM query
  15.     int diff=b-a+1;
  16.     int k=floor(log2(diff));
  17.     int r=pow(2, k);
  18.     return max(V[sparse_table[a][k]], V[sparse_table[b+1-r][k]]);
  19. }
  20.  
  21.  
  22. int valuta(int N, int* H){
  23.    
  24.     //for (int i=0; i<N; i++) V.push_back(H[i]);
  25.     for (int i=0; i<N; i++) V[i]=H[i];
  26.    
  27.    
  28.     //sparse_table.resize(N);    
  29.     int a=floor(log2(N));
  30.     //for (int i=0; i<N; i++) sparse_table[i].push_back(i);
  31.     for (int i=0; i<N; i++) sparse_table[i][0]=i;
  32.    
  33.     int M=N;
  34.     for (int j=1; j<=a; j++) {
  35.         int r=pow(2, j-1);
  36.         M-=r;
  37.        
  38.         for (int i=0; i<M; i++) {
  39.             /*if (H[sparse_table[i][j-1]]>=H[sparse_table[i+r][j-1]]) sparse_table[i].push_back(sparse_table[i][j-1]);
  40.             else sparse_table[i].push_back(sparse_table[i+r][j-1]);*/
  41.            
  42.             if (H[sparse_table[i][j-1]]>=H[sparse_table[i+r][j-1]]) sparse_table[i][j]=sparse_table[i][j-1];
  43.             else sparse_table[i][j]=sparse_table[i+r][j-1];
  44.            
  45.         }
  46.     }
  47.    
  48.    
  49.     //queries
  50.     int conto=0;
  51.     for (int i=1; i<N-1; i++) if (RMQ(0, i)!=H[i] && RMQ(i, N-1)!=H[i]) conto++;
  52.     return conto;
  53. }
  54.  
  55. void progetta(int N, int K, int* H){
  56.     for (int i=0; i<N-K-2; i++) H[i]=i+1;
  57.     H[N-K-2]=N;
  58.     for (int i=N-K-1; i<N; i++) H[i]=i;
  59. }
Advertisement
Add Comment
Please, Sign In to add comment