oj.uz

Submission #1003501

# Submission time Handle Problem Language Result Execution time Memory
1003501 2024-06-20T11:58:52 Z vjudge1 Flooding Wall (BOI24_wall) C++17
12 / 100
 396 ms 72844 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 23896 KB Output is correct
2 Correct 9 ms 23900 KB Output is correct
3 Correct 9 ms 23780 KB Output is correct
4 Correct 9 ms 23896 KB Output is correct
5 Correct 10 ms 23900 KB Output is correct
6 Correct 9 ms 23900 KB Output is correct
7 Correct 10 ms 23952 KB Output is correct
8 Correct 9 ms 23876 KB Output is correct
9 Correct 8 ms 23788 KB Output is correct
10 Correct 8 ms 23900 KB Output is correct
11 Incorrect 14 ms 23900 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 23900 KB Output is correct
2 Correct 9 ms 23792 KB Output is correct
3 Correct 10 ms 23768 KB Output is correct
4 Correct 9 ms 23896 KB Output is correct
5 Correct 9 ms 23900 KB Output is correct
6 Correct 9 ms 23900 KB Output is correct
7 Correct 9 ms 23900 KB Output is correct
8 Correct 8 ms 23900 KB Output is correct
9 Correct 9 ms 23896 KB Output is correct
10 Correct 9 ms 23900 KB Output is correct
11 Correct 9 ms 23948 KB Output is correct
12 Correct 8 ms 23896 KB Output is correct
13 Correct 9 ms 23900 KB Output is correct
14 Correct 9 ms 23900 KB Output is correct
15 Incorrect 11 ms 24408 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 23900 KB Output is correct
2 Correct 9 ms 23792 KB Output is correct
3 Correct 10 ms 23768 KB Output is correct
4 Correct 9 ms 23896 KB Output is correct
5 Correct 9 ms 23900 KB Output is correct
6 Correct 9 ms 23900 KB Output is correct
7 Correct 9 ms 23900 KB Output is correct
8 Correct 8 ms 23900 KB Output is correct
9 Correct 9 ms 23896 KB Output is correct
10 Correct 9 ms 23900 KB Output is correct
11 Correct 9 ms 23948 KB Output is correct
12 Correct 8 ms 23896 KB Output is correct
13 Correct 9 ms 23900 KB Output is correct
14 Correct 9 ms 23900 KB Output is correct
15 Incorrect 11 ms 24408 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 23896 KB Output is correct
2 Correct 9 ms 23900 KB Output is correct
3 Correct 9 ms 23780 KB Output is correct
4 Correct 9 ms 23896 KB Output is correct
5 Correct 10 ms 23900 KB Output is correct
6 Correct 9 ms 23900 KB Output is correct
7 Correct 10 ms 23952 KB Output is correct
8 Correct 9 ms 23876 KB Output is correct
9 Correct 8 ms 23788 KB Output is correct
10 Correct 8 ms 23900 KB Output is correct
11 Incorrect 14 ms 23900 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 23900 KB Output is correct
2 Correct 8 ms 23956 KB Output is correct
3 Correct 8 ms 23900 KB Output is correct
4 Correct 9 ms 23808 KB Output is correct
5 Correct 9 ms 23892 KB Output is correct
6 Correct 9 ms 23864 KB Output is correct
7 Correct 9 ms 23900 KB Output is correct
8 Correct 9 ms 23872 KB Output is correct
9 Correct 10 ms 23900 KB Output is correct
10 Correct 16 ms 24800 KB Output is correct
11 Correct 15 ms 24800 KB Output is correct
12 Correct 15 ms 24936 KB Output is correct
13 Correct 17 ms 24796 KB Output is correct
14 Correct 396 ms 72660 KB Output is correct
15 Correct 380 ms 72628 KB Output is correct
16 Correct 377 ms 72844 KB Output is correct
17 Correct 359 ms 72624 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 23896 KB Output is correct
2 Correct 9 ms 23900 KB Output is correct
3 Correct 9 ms 23780 KB Output is correct
4 Correct 9 ms 23896 KB Output is correct
5 Correct 10 ms 23900 KB Output is correct
6 Correct 9 ms 23900 KB Output is correct
7 Correct 10 ms 23952 KB Output is correct
8 Correct 9 ms 23876 KB Output is correct
9 Correct 8 ms 23788 KB Output is correct
10 Correct 8 ms 23900 KB Output is correct
11 Incorrect 14 ms 23900 KB Output isn't correct
12 Halted 0 ms 0 KB -