Submission #1106983

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106983		VinhLuu	Flooding Wall (BOI24_wall)	C++17	25 / 100	169 ms	255016 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 sub2{
  int sf[5005][5005], sg[5005][5005], f[5005][5005], g[5005][5005];
  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();
    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]);
//        cerr << i << " " << j << " " << f[i][j] << " x\n";
      }
      sf[i][m] = f[i][m];
      for(int j = m - 1; j >= 1; j --) add(sf[i][j], f[i][j] + sf[i][j + 1]);
    }

//    cerr << "    g\n";

    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]);
//        cerr << i << " " << j << " " << g[i][j] << " p\n";
      }
      sg[i][m] = g[i][m];
      for(int j = m - 1; j >= 1; j --) add(sg[i][j], g[i][j] + sg[i][j + 1]);
    }

    int ans = 0;

    for(int i = 2; i < n; i ++){
//      cerr << i << " " << a[i] << " " << b[i] << " phase\n";
      for(int j = 1; j <= m; j ++){
        int high = rrh[j - 1];
        int cnt = (f[i - 1][j] * sg[i + 1][j + 1] % mod + g[i + 1][j] * sf[i - 1][j] % mod) % mod;

//        cerr << j << " " << f[i - 1][j] << " " << sg[i + 1][j + 1] << " " << g[i + 1][j] << " " << sf[i - 1][j] << " o\n";

        if(high > rrh[a[i] - 1]){
          int val = cnt * (high - rrh[a[i] - 1]) % mod;
          add(ans, val);
        }
        if(high > rrh[b[i] - 1]){
          int val = 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];

  sub2 :: 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:87:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |     freopen(task ".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
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 ".out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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