oj.uz

Submission #1003502

# Submission time Handle Problem Language Result Execution time Memory
1003502 2024-06-20T12:00:40 Z vjudge1 Flooding Wall (BOI24_wall) C++17
12 / 100
 386 ms 72856 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]);
  }

    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] > cp[j].second) 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] > cp[j].second) 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 23900 KB Output is correct
2 Correct 9 ms 23856 KB Output is correct
3 Correct 9 ms 23852 KB Output is correct
4 Correct 9 ms 23896 KB Output is correct
5 Correct 10 ms 23772 KB Output is correct
6 Correct 11 ms 23900 KB Output is correct
7 Correct 9 ms 23896 KB Output is correct
8 Correct 8 ms 23808 KB Output is correct
9 Correct 9 ms 23964 KB Output is correct
10 Correct 11 ms 23896 KB Output is correct
11 Incorrect 8 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 10 ms 23900 KB Output is correct
2 Correct 10 ms 23972 KB Output is correct
3 Correct 9 ms 23896 KB Output is correct
4 Correct 10 ms 23900 KB Output is correct
5 Correct 10 ms 23900 KB Output is correct
6 Correct 10 ms 23896 KB Output is correct
7 Correct 11 ms 23896 KB Output is correct
8 Correct 10 ms 23900 KB Output is correct
9 Correct 10 ms 23900 KB Output is correct
10 Correct 9 ms 23900 KB Output is correct
11 Correct 8 ms 23972 KB Output is correct
12 Correct 9 ms 23896 KB Output is correct
13 Correct 9 ms 23896 KB Output is correct
14 Correct 9 ms 23952 KB Output is correct
15 Incorrect 13 ms 24412 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23900 KB Output is correct
2 Correct 10 ms 23972 KB Output is correct
3 Correct 9 ms 23896 KB Output is correct
4 Correct 10 ms 23900 KB Output is correct
5 Correct 10 ms 23900 KB Output is correct
6 Correct 10 ms 23896 KB Output is correct
7 Correct 11 ms 23896 KB Output is correct
8 Correct 10 ms 23900 KB Output is correct
9 Correct 10 ms 23900 KB Output is correct
10 Correct 9 ms 23900 KB Output is correct
11 Correct 8 ms 23972 KB Output is correct
12 Correct 9 ms 23896 KB Output is correct
13 Correct 9 ms 23896 KB Output is correct
14 Correct 9 ms 23952 KB Output is correct
15 Incorrect 13 ms 24412 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 23900 KB Output is correct
2 Correct 9 ms 23856 KB Output is correct
3 Correct 9 ms 23852 KB Output is correct
4 Correct 9 ms 23896 KB Output is correct
5 Correct 10 ms 23772 KB Output is correct
6 Correct 11 ms 23900 KB Output is correct
7 Correct 9 ms 23896 KB Output is correct
8 Correct 8 ms 23808 KB Output is correct
9 Correct 9 ms 23964 KB Output is correct
10 Correct 11 ms 23896 KB Output is correct
11 Incorrect 8 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 10 ms 23900 KB Output is correct
2 Correct 9 ms 23896 KB Output is correct
3 Correct 9 ms 23820 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 10 ms 23896 KB Output is correct
8 Correct 10 ms 23900 KB Output is correct
9 Correct 9 ms 23900 KB Output is correct
10 Correct 14 ms 24864 KB Output is correct
11 Correct 15 ms 24800 KB Output is correct
12 Correct 14 ms 24804 KB Output is correct
13 Correct 14 ms 24796 KB Output is correct
14 Correct 385 ms 72856 KB Output is correct
15 Correct 371 ms 72624 KB Output is correct
16 Correct 361 ms 72724 KB Output is correct
17 Correct 386 ms 72632 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 23900 KB Output is correct
2 Correct 9 ms 23856 KB Output is correct
3 Correct 9 ms 23852 KB Output is correct
4 Correct 9 ms 23896 KB Output is correct
5 Correct 10 ms 23772 KB Output is correct
6 Correct 11 ms 23900 KB Output is correct
7 Correct 9 ms 23896 KB Output is correct
8 Correct 8 ms 23808 KB Output is correct
9 Correct 9 ms 23964 KB Output is correct
10 Correct 11 ms 23896 KB Output is correct
11 Incorrect 8 ms 23900 KB Output isn't correct
12 Halted 0 ms 0 KB -