oj.uz

Submission #915439

# Submission time Handle Problem Language Result Execution time Memory
915439 2024-01-23T22:53:05 Z null_awe Fancy Fence (CEOI20_fancyfence) C++14
0 / 100
 2 ms 464 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pii pair<int, int>

const int MOD = 1e9 + 7;
const int INV2 = 500000004;

int32_t main() {
  int n; cin >> n;
  vector<int> h(n), w(n);
  for (int i = 0; i < n; ++i) cin >> h[i];
  for (int i = 0; i < n; ++i) cin >> w[i];
  stack<int> hsum, area;
  stack<pii> hs;
  hsum.push(0), area.push(0);
  hs.push({0, 0});
  int ans = 0;
  for (int i = 0; i < n; ++i) {
    // add indiv to answer:
    ans += (h[i] * (h[i] + 1) / 2 % MOD) * (w[i] * (w[i] + 1) / 2 % MOD) % MOD;
    // remove unneccesary:
    int nw = 0;
    while (hs.top().first > h[i]) nw += hs.top().second, hsum.pop(), area.pop(), hs.pop();
    // insert (h[i], nw):
    int lh = hs.top().first + 1;
    hsum.push((hsum.top() + (h[i] + lh) % MOD * (h[i] - lh + 1) % MOD * INV2 % MOD) % MOD);
    area.push((area.top() + hsum.top() * nw % MOD) % MOD);
    // add rest to answer:
    ans = (ans + area.top()) % MOD;
    // insert (h[i], w[i]):
    lh = hs.top().first + 1;
    hsum.push((hsum.top() + (h[i] + lh) % MOD * (h[i] - lh + 1) % MOD * INV2 % MOD) % MOD);
    area.push((area.top() + hsum.top() * w[i] % MOD) % MOD);
  }
  cout << ans << '\n';
  return 0;
}


/*
System.out.println("Hello World");
public static double yamom(String "s"){

}
*/

Subtask #1
0.0 / 0.0

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

Subtask #2
0 / 12.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 15.0

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

Subtask #5
0 / 15.0

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

Subtask #6
0 / 18.0

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

Subtask #7
0 / 27.0

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