Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h> //72%. Supera i limiti di memoria
- //#include "grader.cpp"
- using namespace std;
- //vector <int> V;
- //vector <vector <int> > sparse_table;
- int V[1000001];
- int sparse_table[1000001][20];
- int RMQ (int a, int b) { //range MAXIMUM query
- int diff=b-a+1;
- int k=floor(log2(diff));
- int r=pow(2, k);
- return max(V[sparse_table[a][k]], V[sparse_table[b+1-r][k]]);
- }
- int valuta(int N, int* H){
- //for (int i=0; i<N; i++) V.push_back(H[i]);
- for (int i=0; i<N; i++) V[i]=H[i];
- //sparse_table.resize(N);
- int a=floor(log2(N));
- //for (int i=0; i<N; i++) sparse_table[i].push_back(i);
- for (int i=0; i<N; i++) sparse_table[i][0]=i;
- int M=N;
- for (int j=1; j<=a; j++) {
- int r=pow(2, j-1);
- M-=r;
- for (int i=0; i<M; i++) {
- /*if (H[sparse_table[i][j-1]]>=H[sparse_table[i+r][j-1]]) sparse_table[i].push_back(sparse_table[i][j-1]);
- else sparse_table[i].push_back(sparse_table[i+r][j-1]);*/
- if (H[sparse_table[i][j-1]]>=H[sparse_table[i+r][j-1]]) sparse_table[i][j]=sparse_table[i][j-1];
- else sparse_table[i][j]=sparse_table[i+r][j-1];
- }
- }
- //queries
- int conto=0;
- for (int i=1; i<N-1; i++) if (RMQ(0, i)!=H[i] && RMQ(i, N-1)!=H[i]) conto++;
- return conto;
- }
- void progetta(int N, int K, int* H){
- for (int i=0; i<N-K-2; i++) H[i]=i+1;
- H[N-K-2]=N;
- for (int i=N-K-1; i<N; i++) H[i]=i;
- }
Advertisement
Add Comment
Please, Sign In to add comment