oj.uz

Submission #650256

# Submission time Handle Problem Language Result Execution time Memory
650256 2022-10-13T09:01:42 Z alvinpiter Fancy Fence (CEOI20_fancyfence) C++17
55 / 100
 106 ms 4896 KB 
#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 solveBruteForce() {
  int psum[55][55];
  memset(psum, 0, sizeof(psum));
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= h[i]; j++) {
      psum[i][j] = 1;
    }
    cout << endl;
  }

  for (int i = 1; i <= 50; i++) {
    for (int j = 1; j <= 50; j++) {
      psum[i][j] += psum[i - 1][j] + psum[i][j - 1] - psum[i - 1][j - 1];
    }
  }

  int ans = 0;
  for (int i1 = 1; i1 <= 50; i1++) {
    for (int j1 = 1; j1 <= 50; j1++) {
      for (int i2 = i1; i2 <= 50; i2++) {
        for (int j2 = j1; j2 <= 50; j2++) {
          int sum = psum[i2][j2] - psum[i2][j1 - 1] - psum[i1 - 1][j2] + psum[i1 - 1][j1 - 1];
          if (sum == (i2 - i1 + 1) * (j2 - j1 + 1)) {
            ans += 1;
          }
        }
      }
    }
  }

  return ans;
}

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];
  }

  // cout << solveBruteForce() << endl;
  // return 0;

  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();

      if (st.empty()) {
        sumFhw = 0;
      } else {
        LL totalWidth = sumWidth[top] - 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 = 0;
    if (firstLowerIdx != i - 1) {
      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 << "\ni: " << i << endl;
    // cout << "rectanglesOnTheCurrentFence: " << rectanglesOnTheCurrentFence << endl;
    // cout << "rectanglesOnTheCurrentFenceAndTallerNeighbors: " << rectanglesOnTheCurrentFenceAndTallerNeighbors << endl;
    // cout << "rectanglesOnTheCurrentFenceAndLowerNeighbors: " << rectanglesOnTheCurrentFenceAndLowerNeighbors << endl;
    // cout << "sumFhw: " << sumFhw << endl;
  }

  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 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 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 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 30 ms 1960 KB Output is correct
4 Correct 54 ms 3784 KB Output is correct
5 Correct 55 ms 3788 KB Output is correct
6 Correct 55 ms 3676 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 9 ms 468 KB Output is correct
3 Correct 40 ms 1356 KB Output is correct
4 Correct 76 ms 2628 KB Output is correct
5 Correct 106 ms 2548 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 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 8 ms 548 KB Output is correct
4 Correct 40 ms 1356 KB Output is correct
5 Correct 78 ms 2520 KB Output is correct
6 Correct 84 ms 2568 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 12 ms 484 KB Output is correct
9 Correct 45 ms 1544 KB Output is correct
10 Correct 74 ms 3036 KB Output is correct
11 Correct 76 ms 4896 KB Output is correct
12 Correct 1 ms 308 KB Output is correct

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -