답안 #650267

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
650267	2022-10-13T09:35:45 Z	alvinpiter	Fancy Fence (CEOI20_fancyfence)	C++17	100 / 100	102 ms	3296 KB

fancyfence

/*
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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

답안 #650267

Compilation message

Subtask #1 0.0 / 0.0

Subtask #2 12.0 / 12.0

Subtask #3 13.0 / 13.0

Subtask #4 15.0 / 15.0

Subtask #5 15.0 / 15.0

Subtask #6 18.0 / 18.0

Subtask #7 27.0 / 27.0

Subtask #1
0.0 / 0.0

Subtask #2
12.0 / 12.0

Subtask #3
13.0 / 13.0

Subtask #4
15.0 / 15.0

Subtask #5
15.0 / 15.0

Subtask #6
18.0 / 18.0

Subtask #7
27.0 / 27.0