[UVA] 12572 - RMQ Overkill

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 12572 - RMQ Overkill
Source            : UVa Online Judge
Category          : Data Structure
Algorithm         : Histogram Technique
Verdict           : Accepted

1. #include <bits/stdc++.h>  
2.   
3. using namespace std;  
4.   
5. static const int maxn = 1e4 + 5;  
6. static const int mod = 1000000007;  
7.   
8. int arr[maxn];  
9. int Left[maxn], Right[maxn];  
10.   
11. int main()  
12. {  
13.       int n;  
14.       char s[maxn];  
15.       while (scanf("%d", &n) == 1)  
16.       {  
17.             scanf("%s", s);  
18.             for (int i = 0; i < n; i++) arr[i+1] = s[i] - '0'; // make 1 indexed  
19.             for (int i = 1; i <= n; i++)  
20.             {  
21.                   int cnt = 0;  
22.                   int r = i;  
23.                   while (r <= n && arr[r] >= arr[i]) cnt++, r++;  
24.                   Right[i] = cnt;  
25.                   cnt = 0;  
26.                   int l = i-1;  
27.                   while (l >= 1 && arr[l] > arr[i]) cnt++, l--;  
28.                   Left[i] = (Right[i] * cnt);  
29.             }  
30.             int sum = 0;  
31.             for (int i = 1; i <= n; i++)  
32.             {  
33.                   sum += (arr[i] * (Left[i] + Right[i]));  
34.                   if (sum > mod) sum -= mod;  
35.             }  
36.             printf("%d\n", sum);  
37.       }  
38. }