fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <stack>
  4.  
  5. using namespace std;
  6.  
  7. typedef long long ll;
  8. const int MOD = 1e9 + 7;
  9.  
  10. // Funkcja pomocnicza do obliczania n*(n+1)/2 modulo MOD
  11. ll count_pairs(ll n) {
  12.     ll res = (n % MOD) * ((n + 1) % MOD) % MOD;
  13.     return (res * 500000004) % MOD; // 500000004 to odwrotność modularna 2 (mod 10^9 + 7)
  14. }
  15.  
  16. struct Section {
  17.     ll h, w;
  18. };
  19.  
  20. int main() {
  21.     ios_base::sync_with_stdio(false);
  22.     cin.tie(NULL);
  23.  
  24.     int N;
  25.     cin >> N;
  26.  
  27.     vector<ll> h(N), w(N);
  28.     for (int i = 0; i < N; i++) cin >> h[i];
  29.     for (int i = 0; i < N; i++) cin >> w[i];
  30.  
  31.     stack<Section> s;
  32.     ll total_rectangles = 0;
  33.  
  34.     for (int i = 0; i <= N; i++) {
  35.         ll cur_h = (i == N) ? 0 : h[i];
  36.         ll cur_w = 0;
  37.  
  38.         while (!s.empty() && s.top().h >= cur_h) {
  39.             Section top = s.top();
  40.             s.pop();
  41.  
  42.             ll left_h = (s.empty() ? 0 : s.top().h);
  43.             // Wybieramy wysokość graniczną (wyższą z cur_h i wysokości poprzedniego elementu na stosie)
  44.             ll max_prev_h = max(left_h, cur_h);
  45.  
  46.             // Liczymy prostokąty, które mieszczą się w "pasku" od max_prev_h do top.h
  47.             ll h_options = (count_pairs(top.h) - count_pairs(max_prev_h) + MOD) % MOD;
  48.             ll w_options = count_pairs(top.w + cur_w);
  49.  
  50.             total_rectangles = (total_rectangles + (h_options * w_options) % MOD) % MOD;
  51.  
  52.             // Łączymy szerokość "przerobionego" prostokąta z aktualną szerokością dla następnych kroków
  53.             cur_w = (cur_w + top.w) % MOD;
  54.         }
  55.  
  56.         if (cur_h > 0) {
  57.             s.push({cur_h, (w[i] + cur_w) % MOD});
  58.         }
  59.     }
  60.  
  61.     cout << total_rectangles << endl;
  62.  
  63.     return 0;
  64. }
Success #stdin #stdout 0.01s 5296KB
comments (?)
stdin
copy 
2
1 2
1 2
stdout
copy 
12
https://ideone.com/wE4hTA
language:
C++14 (gcc 8.3)
created:
7 hours 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!