fork(2) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int MAX = 500005;
  6. const int MOD = 1000000007;
  7.  
  8. int N;
  9. int A[MAX];
  10. int s[MAX];
  11. int index_left[MAX];
  12. int L_max[MAX];
  13. int R_max[MAX];
  14. int dp[MAX];
  15. int prefix_sum[MAX];
  16.  
  17. int sum(int l, int r) {
  18.   if (l == 0) return prefix_sum[r];
  19.   return (prefix_sum[r] - prefix_sum[l - 1]) % MOD;
  20. }
  21.  
  22. int solve() {
  23.   // index_left[i] = Largest index j <= i and such that A[j..i] obeys the first
  24.   // condition i.e. min(A[j..i]) <= (i - j + 1).
  25.   // If index_left[i] <= 0, then no such 'j' exists.
  26.   // We use dequeue where we maintain a strictly growing value of A[i].
  27.   int l = 1, r = 0;
  28.   for (int i = 1; i <= N; i++) {
  29.     while (l <= r && A[i] <= A[s[r]]) {
  30.       r--;
  31.     }
  32.     s[++r] = i;
  33.     // We try to find the largest value of 'j'. So, we try to left shift till
  34.     // it is possible to do so.
  35.     while (l < r && min(s[l], i - A[s[l]] + 1) <= min(s[l + 1], i - A[s[l + 1]] + 1)) {
  36.       l++;
  37.     }
  38.     index_left[i] = min(s[l], i - A[s[l]] + 1);
  39.   }
  40.   // L_max[i] = Largest index j < i such that A[j] > A[i]. If no such index "j"
  41.   // exists, we let L_max[i] = 0.
  42.   // It can be solved using stack using a modification of "stock span problem".
  43.   // You can look at https://w...content-available-to-author-only...s.org/the-stock-span-problem/
  44.   // for more details. The author uses idea similar to failure function in
  45.   // kmp algorithm. The complexity is O(N). Here failing for index "i" means
  46.   // going to largest index "j" such that A[j] > A[i].
  47.   for (int i = 1; i <= N; i++) {
  48.     int curr = i - 1;
  49.     while (curr != 0 && A[curr] <= A[i]) {
  50.       curr = L_max[curr];
  51.     }
  52.     L_max[i] = curr;
  53.   }
  54.   // R_max[i] = Smallest index j > i such that A[j] >= A[i]. If no such index "j"
  55.   // exixts, we let R_max[i] = N + 1;
  56.   // Calculation is similar to L_max[i]. Complexity is O(N).
  57.   for (int i = N; i >= 1; i--) {
  58.     int curr = i + 1;
  59.     while (curr <= N && A[curr] < A[i]) {
  60.       curr = R_max[curr];
  61.     }
  62.     R_max[i] = curr;
  63.   }
  64.  
  65.   // Complexity of the code till now is O(N) for all the 3 loops. :)
  66.  
  67.   // dp[i] denotes number of valid partitions in the array A[1..i].
  68.   // prefix_sum[i] = sum_{x=1}^{x=i} dp[x]
  69.   for (int i = 1; i <= N; i++) {
  70.     dp[i] = 0;
  71.   }
  72.   // Number of partition for null sequence is 1.
  73.   dp[0] = 1;
  74.   prefix_sum[0] = 1;
  75.   int currSum = 0;
  76.   for (int i = 1; i <= N; i++) {
  77.     // We assume all the values of dp[i-1] and prefix sum of dp is calculated
  78.     // correctly before this loop. This is the inductive hypothesis and we try
  79.     // to calculate the correct value of dp[i] in this iteration and thus add it
  80.     // to prefix sum as well to make sure it is correctly calculated.
  81.  
  82.     // currSum takes care of the following 2 cases:
  83.     // 1. Sum of all paritions where index 'j' is part of partition obeying the
  84.     //    second condition and A[j] was the maximum in the partition.
  85.     // 2. The faulty paritions containing 'i' which obeyed first condition but
  86.     //    did not obtain the second condition. This is already stored in dp[i]
  87.     //    by subtracting contribution from 1 to (i-1) wherever applicable. Note
  88.     //    that dp[i] was initialised with 0 and can only be negative at this
  89.     //    moment to due subtraction by faulty values.
  90.     currSum = (currSum + dp[i]) % MOD;
  91.  
  92.     // Condition 2 of safe parition is:
  93.     // Length of partition <= Maximum in the partition.
  94.     // We need to find subarrays where condition 2 is obeyed and A[i] is the
  95.     // maximum in the subarray.
  96.     // By definition of L_max[i] and R_max[i], A[i] in maximum in [l..r] where
  97.     // L_max[i] <= l <= i and i <= r <= R_max[i]
  98.     // Note that for calculating dp[i], we need a valid partition from
  99.     // [(j+1)..i] where j < i and add the contribution of dp[j] to dp[i].
  100.     // So, we need to consider subarrays ending at 'i' only which simplifies the
  101.     // problem a bit. So for [(j+1)..i], the condition is
  102.     // (i - j) <= A[i]
  103.     // j >= (i - A[i])
  104.     // We also want A[i] to be maximum, so the valid positions should start
  105.     // after L_max[i] by definition.
  106.     // This explains the below values for variable 'l' and 'r'.
  107.     int l = max(i - A[i], L_max[i]);
  108.     int r = i - 1;
  109.  
  110.     // add dp[l..r] to currSum where we add the contribution of part 1 as per
  111.     // definition of currSum on line 83.
  112.     currSum = (currSum + sum(l, r)) % MOD;
  113.  
  114.     // Find the exact value of dp[i].
  115.     if (index_left[i] <= 0) {
  116.       // If A[1..i] doesn't obey condition 1, then even if we partition it into
  117.       // smaller parts where initial part obey both condition 1 and 2, the last
  118.       // partition containing 'i' will still not obey condition 1. This is due
  119.       // to the defintion of index_left for finding the maximum possible 'j' for
  120.       // every index.
  121.       dp[i] = 0;
  122.     }
  123.     else {
  124.       // If A[1..i] obeys the condition 1, then any subarray from [j..i] where
  125.       // index_left[i] <= j <= i-1 is not safe as first condition is not obeyed
  126.       // as per defintion of index_left[i].
  127.       // Consider this scenario as trying to add dp[j] to dp[i] in brute force
  128.       // algorithm but it is not possible as [j..i] is not safe.
  129.       // Note that part 1 for defintion in currSum on line 83 can violate
  130.       // condition 1 and this basically takes care of such situations.
  131.       dp[i] = (currSum - sum(index_left[i], i - 1)) % MOD;
  132.     }
  133.     // Handle the case of negative modulus.
  134.     if (dp[i] < 0) {
  135.       dp[i] = (dp[i] + MOD) % MOD;
  136.     }
  137.     // Update the prefix_sum array.
  138.     prefix_sum[i] = (prefix_sum[i - 1] + dp[i]) % MOD;
  139.  
  140.     // Now we want to want faulty subarrays where A[i] was the maximum, the
  141.     // first condition was obeyed by the second condition was violated and
  142.     // subtract the value of faulty partitions from the respective dp[] i.e. we
  143.     // are solving for condition 2 for currSum on line 85.
  144.     // Now for such subarrays we know their left end point should start before
  145.     // index 'i' and their right end points has to end before R_max[i].
  146.     // curr is set as 'l' as it the starting point where A[i] can be maximum as
  147.     // explained before.
  148.     // The subarray being considered is [curr..x]. To disobey second condition
  149.     // the length should be greater than maximum i.e. A[i]
  150.     // length > A[i].
  151.     // So, for given curr, the first such right end point is (curr + A[i] + 1)
  152.     // This should be less than or equal to R_max[i].
  153.     // If this is less than R_max[i], then curr is the only such left end point
  154.     // for a fixed end point as moving forward, the length of partition
  155.     // decreases but maximum still remains A[i], which doesn't lead to violation
  156.     // of condition 2.
  157.     int curr = l;
  158.     while (curr < i && curr + A[i] + 1 < R_max[i]) {
  159.       dp[curr + A[i] + 1] = (dp[curr + A[i] + 1] - dp[curr]) % MOD;
  160.       curr++;
  161.     }
  162.     if (curr + A[i] + 1 >= R_max[i]) {
  163.       // If need to check for greater or equal than and subtract a range sum
  164.       // here as all subarrays will have right end point as R_max[i] and left
  165.       // end point from [curr..r] but can't have A[i] as the maximum.
  166.       // Consider this scenario as trying to add dp[curr] to dp[R_max[i]] in
  167.       // brute force algorithm but it is not possible as subarray
  168.       // [(cur+1)..R_max[i]] is not safe as second condtion is violated.
  169.       dp[R_max[i]] = (dp[R_max[i]] - sum(curr, r)) % MOD;
  170.     }
  171.   }
  172.   /*
  173.   Complexity Analysis of above loop:
  174.   Note that all operations are O(1) except the while loop from line 158 to 161.
  175.  
  176.   For the analysis of this while loop over all possible indices 'i', let we
  177.   consider the 2 sceanrios for variable 'l' on line 107.
  178.  
  179.   Case 1: l = i - A[i]
  180.   The total movement in while loop in this case is
  181.   O(min(A[i], R_max[i] - i))
  182.  
  183.   Case 2: l = L_max[i]
  184.   The total movement in while loop in this case is
  185.   O(min(i - L_max[i], R_max[i] - L_max[i] - A[i]))
  186.  
  187.   Neglect the +1/-1 in above calculations, we are representing Big-O complexity.
  188.  
  189.   Let's try to do a naive calculation where in case 1, we always end up using
  190.   (R_max[i] - i) and in second case we always end up using (i - L_max[i]). In
  191.   case, this was not the case, the number of movement just decreases, so be are
  192.   better off in that case.
  193.  
  194.   Now, we try to chose the largest possible position of 'l' to start from in
  195.   line 107. So, for every index 'i' we will end up using minimum of above 2
  196.   movements, i.e. min(i - L_max[i], R_max[i] - i)
  197.  
  198.   This means for every index we end up chosing the smallest subarray, either to
  199.   left or right side where A[i] is maximum.
  200.  
  201.   Theoretically, we can have the span for every index 'i' as the whole subarray
  202.   where it is maximum. i.e. R_max[i] - L_max[i] ~ O(N).
  203.  
  204.   So, the overall complexity analysis is sum_{i=1}^{i=N} O(min(a, b)) where
  205.   O(a) + O(b) = O(N).
  206.  
  207.   Using the detailed analysis from https://c...content-available-to-author-only...s.com/blog/entry/56345,
  208.   our complexity for this part of O(N logN), which is a very loose upper bound.
  209.   */
  210.   return dp[N];
  211. }
  212.  
  213. int main() {
  214.   // Input.
  215.   scanf("%d", &N);
  216.   for (int i = 1; i <= N; ++i) {
  217.     scanf("%d", &A[i]);
  218.   }
  219.   printf("%d\n", solve());
  220.   return 0;
  221. }
  222.  
  223. /*
  224. Some testcases:
  225. 7
  226. 1 6 2 3 4 3 4
  227.  
  228. 15
  229. 1 1 2 3 5 5 6 7 7 10 10 11 12
  230.  
  231. 15
  232. 2 1 2 3 4 2 1 3 2 4 3 1 4 2 5
  233. */
  234.  
  235.  
Success #stdin #stdout 0s 28912KB
comments (?)
stdin
copy 
7
1 6 2 3 4 3 4
stdout
copy 
6
https://ideone.com/Jipp2L
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!