Submission #1003421

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003421		vjudge1	Flooding Wall (BOI24_wall)	C++17	56 / 100	2533 ms	1048576 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define all(x) x.begin(), x.end()

const int N = 5e5+5, mod = 1e9+7;

int n, mx, a[N], b[N], c[N], pre2[N], suf2[N];
vector<int> pre[N], suf[N];

int pw(int x, int y) {
  return (!y ? 1 : pw(x*x % mod, y/2) * (y%2 ? x : 1) % mod);
}

signed main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n;
  mx = 1;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  for (int i = 0; i < n; i++) {
    cin >> b[i];
    if (a[i] > b[i]) swap(a[i], b[i]);
    mx = max(mx, b[i]);
  }

  if (n <= 20) {
    int ans = 0;
    for (int mask = 0; mask < (1 << n); mask++) {
      for (int i = 0; i < n; i++) {
        c[i] = a[i];

        if ((mask >> i) & 1) c[i] = b[i];
      }

      for (int i = 0; i < n; i++) {
        pre2[i] = max((i ? pre2[i-1] : 1), c[i]);
      }

      for (int i = n-1; i >= 0; i--) {
        suf2[i] = max((i+1 < n ? suf2[i+1] : 1), c[i]);
      }

      for (int i = 1; i < n-1; i++) {
        if (c[i] < min(pre2[i-1], suf2[i+1])) {
          ans += min(pre2[i-1], suf2[i+1]) - c[i];
          ans %= mod;
        }
      }
    }

    cout << ans << "\n";
  }
  else {
    for (int i = 0; i < n; i++) {
      pre[i].resize(mx+1);
      suf[i].resize(mx+1);
    }

    for (int i = 0; i < n; i++) {
      for (int j = 0; j <= mx; j++) {
        pre[i][j] = (i ? pre[i-1][j] : 1);
        
        if (b[i] <= j) {
          pre[i][j] *= 2;
          pre[i][j] %= mod;
        }
        else if (a[i] > j) pre[i][j] = 0;
      }
    }

    for (int i = n-1; i >= 0; i--) {
      for (int j = 0; j <= mx; j++) {
        suf[i][j] = (i+1 < n ? suf[i+1][j] : 1);
        
        if (b[i] <= j) {
          suf[i][j] *= 2;
          suf[i][j] %= mod;
        }
        else if (a[i] > j) suf[i][j] = 0;
      }
    }

    int ans = 0;
    for (int i = 1; i < n-1; i++) {
      for (int j = 1; j <= mx; j++) {
        int x = 0;

        x += pw(2, n-1-i) * pre[i-1][j-1] % mod;
        x %= mod;

        x += pw(2, i) * suf[i+1][j-1] % mod;
        x %= mod;

        x = (x - pre[i-1][j-1] * suf[i+1][j-1] % mod + mod) % mod;
        
        //cerr << i << " " << j << " " << x << endl;

        if (a[i] < j) {
          ans += (pw(2, n-1) - x + mod) % mod;
          ans %= mod;
        }

        if (b[i] < j) {
          ans += (pw(2, n-1) - x + mod) % mod;
          ans %= mod;
        }
      }
    }

    cout << ans << "\n";
  }
}

• Subtask 1: 8 / 8
• Subtask 2: 17 / 17
• Subtask 3: 19 / 19
• Subtask 4: 0 / 14
• Subtask 5: 12 / 12
• Subtask 6: 0 / 30