-
Notifications
You must be signed in to change notification settings - Fork 1
/
RMQSparseTable.cpp
47 lines (47 loc) · 1.09 KB
/
RMQSparseTable.cpp
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
#include<bits/stdc++.h>
using namespace std;
#define LOG(n) log(n)/log(2)
int query(int l,int r,int table[100][100],int a[])
{
int k=LOG(r-l+1);
int x=r-pow(2,k);
int y=r-pow(2,k)+1;
return min(a[table[l][k]],a[table[y][k]]);
}
int main()
{
int a[]={4,6,1,5,7,3};
int n=6;
int m=LOG(n)+1;
int table[100][100];
int i,j,k;
for(i=0;i<n;i++)
for(j=0;j<m;j++)
table[i][j]=-1;
for(i=0;i<n;i++)
table[i][0]=i;
for(j=1;j<m;j++)
{
for(i=0;i+pow(2,j)-1<n;i++)
{
int x=pow(2,j-1);
if(a[table[i][j-1]]<a[table[i+x][j-1]])
table[i][j]=table[i][j-1];
else
table[i][j]=table[i+x][j-1];
}
}
for(i=0;i<n;i++)
{
for(j=i;j<n;j++)
{
int mi=INT_MAX;
for(k=i;k<=j;k++)
mi=min(mi,a[k]);
if(mi!=query(i,j,table,a))
{cout<<"Wrong Answer"<<i<<j<<endl;return 0;}
}
}
cout<<"Accepted";
return 0;
}