oj.uz

Submission #650267

# Submission time Handle Problem Language Result Execution time Memory
650267 2022-10-13T09:35:45 Z alvinpiter Fancy Fence (CEOI20_fancyfence) C++17
100 / 100
 102 ms 3296 KB 
/*
Assume we already know the number of rectangles on the first (i - 1) fence.

Define f(i) as (i * i + i)/2;

If we are to add the i-th fence, then the new rectangles can be categorized into 3:
* It lies completely on the i-th fence. There are f(h[i]) * f(w[i]) such rectangles.
* The right end ends on the i-th fence while the left end lies on taller fence to the left of it.
  We don't want to consider the taller fence that comes before a fence lower than the i-th fence.
  Let's say the first lower fence to the left of the i-th fence is the j-th fence.
  There are (sumWidth(j + 1, i) * w[i]) * f(h[i]) such rectangles.
* The right end ends on the i-th fence while the left end lies on lower fences.
  Assume we keep the lower fences on a stack:

  h_i1 < h_i2 < h_i3 ...
  We can create rectangles whose height is at most h_i3 using the (i2 + 1)-th fence upto the i3-th fence.
  There are (sumWidth(i2 + 1, i3) * w[i]) * f(h_i3) such rectangles.

  We can do the same calculation for the (i1 + 1)-th fence upto the i2-th fence, and so on.
*/

#include<bits/stdc++.h>
using namespace std;
#define LL long long int
#define MOD 1000000007
#define MAXN 100000

int n;
LL h[MAXN + 3], w[MAXN + 3], sumWidth[MAXN + 3], sumFhw = 0, ans = 0;
stack<int> st;

LL f(LL k) {
  LL k1 = k + 1;
  return k%2 == 0 ? ((k/2)%MOD * (k1)%MOD)%MOD : (k%MOD * (k1/2)%MOD)%MOD;
}

int main() {
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> h[i];
  }

  sumWidth[0] = 0;
  for (int i = 1; i <= n; i++) {
    cin >> w[i];
    sumWidth[i] = sumWidth[i - 1] + w[i];
  }

  for (int i = 1; i <= n; i++) {
    LL rectanglesOnTheCurrentFence = (f(h[i]) * f(w[i]))%MOD;
    ans = (ans + rectanglesOnTheCurrentFence)%MOD;

    while (!st.empty() && h[st.top()] >= h[i]) {
      int top = st.top(); st.pop();

      LL totalWidth = sumWidth[top] - (st.empty() ? 0 : sumWidth[st.top()]);
      LL fhw = (f(h[top]) * (totalWidth%MOD))%MOD;
      sumFhw = (sumFhw - fhw + MOD)%MOD;
    }

    int firstLowerIdx = (st.empty() ? 0 : st.top());

    LL rectanglesOnTheCurrentFenceAndTallerNeighbors = (((sumWidth[i - 1] - sumWidth[firstLowerIdx])%MOD * w[i])%MOD * f(h[i]))%MOD;
    ans = (ans + rectanglesOnTheCurrentFenceAndTallerNeighbors)%MOD;

    LL rectanglesOnTheCurrentFenceAndLowerNeighbors = (sumFhw * w[i])%MOD;
    ans = (ans + rectanglesOnTheCurrentFenceAndLowerNeighbors)%MOD;

    LL totalWidth = sumWidth[i] - (st.empty() ? 0 : sumWidth[st.top()]);
    sumFhw = (sumFhw + (f(h[i]) * (totalWidth%MOD))%MOD)%MOD;

    st.push(i);
  }

  cout << ans << endl;
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 31 ms 1516 KB Output is correct
4 Correct 58 ms 2652 KB Output is correct
5 Correct 53 ms 2672 KB Output is correct
6 Correct 57 ms 2728 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 12 ms 664 KB Output is correct
3 Correct 42 ms 1564 KB Output is correct
4 Correct 85 ms 2756 KB Output is correct
5 Correct 82 ms 2680 KB Output is correct
6 Correct 1 ms 212 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 10 ms 572 KB Output is correct
4 Correct 42 ms 1684 KB Output is correct
5 Correct 81 ms 2736 KB Output is correct
6 Correct 96 ms 2764 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 9 ms 624 KB Output is correct
9 Correct 41 ms 1616 KB Output is correct
10 Correct 87 ms 3184 KB Output is correct
11 Correct 77 ms 3076 KB Output is correct
12 Correct 1 ms 212 KB Output is correct

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 2 ms 444 KB Output is correct
14 Correct 2 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 212 KB Output is correct

Subtask #7
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 304 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 30 ms 1720 KB Output is correct
12 Correct 59 ms 2780 KB Output is correct
13 Correct 60 ms 2764 KB Output is correct
14 Correct 64 ms 2848 KB Output is correct
15 Correct 2 ms 340 KB Output is correct
16 Correct 8 ms 724 KB Output is correct
17 Correct 44 ms 1648 KB Output is correct
18 Correct 87 ms 2868 KB Output is correct
19 Correct 102 ms 2832 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 9 ms 684 KB Output is correct
22 Correct 44 ms 1756 KB Output is correct
23 Correct 76 ms 3188 KB Output is correct
24 Correct 88 ms 3296 KB Output is correct
25 Correct 2 ms 256 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 2 ms 340 KB Output is correct
28 Correct 2 ms 340 KB Output is correct
29 Correct 1 ms 344 KB Output is correct
30 Correct 10 ms 724 KB Output is correct
31 Correct 9 ms 696 KB Output is correct
32 Correct 40 ms 1612 KB Output is correct
33 Correct 42 ms 1664 KB Output is correct
34 Correct 73 ms 2952 KB Output is correct
35 Correct 77 ms 2892 KB Output is correct
36 Correct 99 ms 2856 KB Output is correct
37 Correct 84 ms 2796 KB Output is correct
38 Correct 1 ms 212 KB Output is correct
39 Correct 82 ms 2892 KB Output is correct
40 Correct 81 ms 2876 KB Output is correct
41 Correct 79 ms 2900 KB Output is correct
42 Correct 85 ms 3004 KB Output is correct