Submission #1342898

#TimeUsernameProblemLanguageResultExecution timeMemory
1342898ramzialoulouFlooding Wall (BOI24_wall)C++20
56 / 100
977 ms1114112 KiB
#include <bits/stdc++.h>
 
using namespace std;

const int md = int(1e9) + 7;

int mul(int a, int b) {
  return 1LL * a * b % md;
}

void add(int& a, int b) {
  a += b;
  if (a >= md) a -= md;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  cin >> n;
  vector<int> a(n + 1);
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  vector<int> b(n + 1);
  for (int i = 1; i <= n; i++) {
    cin >> b[i];
  }
  auto c = a;
  c.insert(c.end(), b.begin(), b.end());
  c.push_back(0);
  sort(c.begin(), c.end());
  c.erase(unique(c.begin(), c.end()), c.end());
  int m = int(c.size());
  vector idx(2, vector<int>(n + 1));
  for (int i = 1; i <= n; i++) {
    idx[0][i] = lower_bound(c.begin(), c.end(), a[i]) - c.begin();
    idx[1][i] = lower_bound(c.begin(), c.end(), b[i]) - c.begin();
  }
  vector dpL(n + 1, vector<int>(m + 1));
  dpL[0][0] = 1;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      int ka = (c[j] > a[i + 1] ? j : idx[0][i + 1]);
      int kb = (c[j] > b[i + 1] ? j : idx[1][i + 1]);
      add(dpL[i + 1][ka], dpL[i][j]);
      add(dpL[i + 1][kb], dpL[i][j]);
    }
  }
  vector dpR(n + 2, vector<int>(m + 1));
  dpR[n + 1][0] = 1;
  for (int i = n + 1; i >= 1; i--) {
    for (int j = 0; j < m; j++) {
      int ka = (c[j] > a[i - 1] ? j : idx[0][i - 1]);
      int kb = (c[j] > b[i - 1] ? j : idx[1][i - 1]);
      add(dpR[i - 1][ka], dpR[i][j]);
      add(dpR[i - 1][kb], dpR[i][j]);
    }
  }
  vector pre(n + 1, vector<int>(m + 2));
  for (int i = 1; i <= n; i++) {
    for (int j = m - 1; j >= 1; j--) {
      add(pre[i][j], pre[i][j + 1]);
      add(pre[i][j], dpL[i][j]);
    }
  }
  vector suf(n + 1, vector<int>(m + 2));
  for (int i = n; i >= 1; i--) {
    for (int j = m - 1; j >= 1; j--) {
      add(suf[i][j], suf[i][j + 1]);
      add(suf[i][j], dpR[i][j]);
    }
  }
  int ans = 0;
  for (int i = 2; i < n; i++) {
    for (int x : {a[i], b[i]}) {
      for (int j = 0; j < m; j++) {
        if (c[j] <= x) continue;
        int gL = pre[i - 1][j + 1];
        int gR = suf[i + 1][j + 1];
        int L = dpL[i - 1][j];
        int R = dpR[i + 1][j];
        int d = c[j] - x;
        add(ans, mul(d, mul(L, gR)));
        add(ans, mul(d, mul(R, gL)));
        add(ans, mul(d, mul(L, R)));
      }
    }
  }
  cout << ans << '\n';
  return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...