제출 #1095826

#제출 시각아이디문제언어결과실행 시간메모리
1095826SalihSahinFlooding Wall (BOI24_wall)C++14
56 / 100
5021 ms64988 KiB
#include <bits/stdc++.h>
#define pb push_back
#define int long long
using namespace std;

const int N = 2e5 + 5;
const int K = 20;
const int mod = 1e9 + 7;

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n;
    cin>>n;
    set<int> dfvals;
    vector<int> a(n), b(n);
    for(int i = 0; i < n; i++){
        cin>>a[i];
        dfvals.insert(a[i]);
    }
    for(int i = 0; i < n; i++){
        cin>>b[i];
        dfvals.insert(b[i]);
    }
    int ans = 0;
    for(auto itr: dfvals){
        vector<vector<int> > pre(n+1, vector<int>(3)), suf(n+1, vector<int>(3)); // 0 => max < itr, 1 => max = itr, 2 => max > itr
        pre[0][0] = 1;
        for(int i = 0; i < n; i++){
            if(a[i] < itr){
                pre[i+1][0] += pre[i][0];
                pre[i+1][1] += pre[i][1];
                pre[i+1][2] += pre[i][2];
            }
            else if(a[i] == itr){
                pre[i+1][1] += pre[i][0];
                pre[i+1][1] += pre[i][1];
                pre[i+1][2] += pre[i][2];
            }
            else{
                pre[i+1][2] += (pre[i][0] + pre[i][1] + pre[i][2]);
            }
            for(int j = 0; j < 3; j++) pre[i+1][j] %= mod;

            if(b[i] < itr){
                pre[i+1][0] += pre[i][0];
                pre[i+1][1] += pre[i][1];
                pre[i+1][2] += pre[i][2];
            }
            else if(b[i] == itr){
                pre[i+1][1] += (pre[i][0] + pre[i][1]);
                pre[i+1][2] += pre[i][2];
            }
            else{
                pre[i+1][2] += (pre[i][0] + pre[i][1] + pre[i][2]);
            }
            for(int j = 0; j < 3; j++) pre[i+1][j] %= mod;
        }

        suf[n][0] = 1;
        for(int i = n-1; i >= 0; i--){
            if(a[i] < itr){
                suf[i][0] += suf[i+1][0];
                suf[i][1] += suf[i+1][1];
                suf[i][2] += suf[i+1][2];
            }
            else if(a[i] == itr){
                suf[i][1] += suf[i+1][0];
                suf[i][1] += suf[i+1][1];
                suf[i][2] += suf[i+1][2];
            }
            else{
                suf[i][2] += (suf[i+1][0] + suf[i+1][1] + suf[i+1][2]);
            }
            for(int j = 0; j < 3; j++) suf[i][j] %= mod;

            if(b[i] < itr){
                suf[i][0] += suf[i+1][0];
                suf[i][1] += suf[i+1][1];
                suf[i][2] += suf[i+1][2];
            }
            else if(b[i] == itr){
                suf[i][1] += suf[i+1][0];
                suf[i][1] += suf[i+1][1];
                suf[i][2] += suf[i+1][2];
            }
            else{
                suf[i][2] += (suf[i+1][0] + suf[i+1][1] + suf[i+1][2]);
            }
            for(int j = 0; j < 3; j++) suf[i][j] %= mod;
        }

        int add = 0;
        for(int i = 1; i < n-1; i++){
            int calc = (pre[i][1] * suf[i+1][1] + pre[i][2] * suf[i+1][1] + pre[i][1] * suf[i+1][2])%mod;
            int tot = max(0LL, itr - a[i]) + max(0LL, itr - b[i]);
            add = (add + (calc * tot)%mod)%mod;
        }
        ans = (ans + add)%mod;
    }

    cout<<ans<<endl;
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...