Submission #1003501

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003501		vjudge1	Flooding Wall (BOI24_wall)	C++17	12 / 100	396 ms	72844 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, a[N], b[N], c[N], pre2[N], suf2[N];
vector<int> pre[N], suf[N];
vector<pair<int, int>> cp;

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

  /*if (n <= 0) {
    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 {*/
    vector<int> u;
    u.push_back(0);
    for (int i = 0; i < n; i++) {
      u.push_back(a[i]);
      u.push_back(b[i]);
    }
    sort(all(u));
    u.erase(unique(all(u)), u.end());

    int sz = u.size();
    for (int i = 0; i < sz; i++) {
      cp.push_back(make_pair(u[i], u[i]));

      if (i+1 < sz && u[i]+1 <= u[i+1]-1) cp.push_back(make_pair(u[i]+1, u[i+1]-1));
    }
    sz = cp.size();

    for (int i = 0; i < n; i++) {
      pre[i].resize(sz);
      suf[i].resize(sz);
    }

    for (int i = 0; i < n; i++) {
      for (int j = 0; j < sz; j++) {
        pre[i][j] = (i ? pre[i-1][j] : 1);
        
        if (b[i] <= cp[j].second) {
          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 < sz; j++) {
        suf[i][j] = (i+1 < n ? suf[i+1][j] : 1);
        
        if (b[i] <= cp[j].second) {
          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 < sz; 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;

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

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

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

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