Submission #1106995

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106995		VinhLuu	Flooding Wall (BOI24_wall)	C++17	44 / 100	740 ms	1048576 KiB

Main

#include <bits/stdc++.h>
//#define int long long
#define ll long long
#define all(lpv) lpv.begin(), lpv.end()
#define fi first
#define se second

using namespace std;

typedef pair<int,int> pii;
const int N = 5e5 + 25;
//const int oo = -1e16;
const int mod = 1e9 + 7;

int n, m, a[N], b[N];

void add(int &x,int y){
  x = (x + y) % mod;
}


namespace sub5{
  vector<int> f[10004], g[10004];

  void solve(){
    vector<int> rrh;
    for(int i = 1; i <= n; i ++){
      rrh.push_back(a[i]);
      rrh.push_back(b[i]);
    }
    sort(all(rrh)); rrh.resize(unique(all(rrh)) - rrh.begin());
    for(int i = 1; i <= n; i ++){
      a[i] = lower_bound(all(rrh), a[i]) - rrh.begin() + 1;
      b[i] = lower_bound(all(rrh), b[i]) - rrh.begin() + 1;
    }
    m = rrh.size();

    for(int i = 0; i <= n + 1; i ++){
      f[i] = vector<int>(m + 2, 0);
      g[i] = vector<int>(m + 2, 0);
    }

    f[0][0] = 1;
    g[n + 1][0] = 1;
    for(int i = 0; i <= n; i ++){
      for(int j = 0; j <= m; j ++) if(f[i][j]){
        add(f[i + 1][max(j, a[i + 1])], f[i][j]);
        add(f[i + 1][max(j, b[i + 1])], f[i][j]);
      }

      for(int j = m - 1; j >= 1; j --) add(f[i][j], f[i][j + 1]);
    }

    for(int i = n + 1; i >= 1;  i--){
      for(int j = 0; j <= m; j ++) if(g[i][j]){
        add(g[i - 1][max(j, a[i - 1])], g[i][j]);
        add(g[i - 1][max(j, b[i - 1])], g[i][j]);
      }
      for(int j = m - 1; j >= 1; j --) add(g[i][j], g[i][j + 1]);
    }

    int ans = 0;

    for(int i = 2; i < n; i ++){
      for(int j = 1; j <= m; j ++){
        int high = rrh[j - 1];
        ll cnt = (1ll * (f[i - 1][j] + mod - f[i - 1][j + 1]) % mod * g[i + 1][j + 1] % mod
                  + 1ll * (g[i + 1][j] + mod - g[i + 1][j + 1]) % mod * f[i - 1][j] % mod) % mod;

        if(high > rrh[a[i] - 1]){
          ll val = 1ll * cnt * (high - rrh[a[i] - 1]) % mod;
          add(ans, val);
        }
        if(high > rrh[b[i] - 1]){
          ll val = 1ll * cnt * (high - rrh[b[i] - 1]) % mod;
          add(ans, val);
        }
      }
    }
    cout << ans;
  }
}

signed main() {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #define task "v"
  if(fopen(task ".inp","r")){
    freopen(task ".inp","r",stdin);
    freopen(task ".out","w",stdout);
  }

  cin >> n;
  for(int i = 1; i <= n; i ++) cin >> a[i];
  for(int i = 1; i <= n; i ++) cin >> b[i];

  sub5 :: solve();
}

/*

10
1 2 3 4 5 6 7 8 9 10
10 9 8 7 6 5 4 3 2 1

*/

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:88:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |     freopen(task ".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:89:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |     freopen(task ".out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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