Submission #1095832

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095832		SalihSahin	Flooding Wall (BOI24_wall)	C++14	12 / 100	132 ms	64960 KiB

Main

#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;
    map<int, int> cnt;
    vector<int> a(n), b(n);
    for(int i = 0; i < n; i++){
        cin>>a[i];
        cnt[a[i]]++;
        if(cnt[a[i]] > 1) dfvals.insert(a[i]);
    }
    for(int i = 0; i < n; i++){
        cin>>b[i];
        cnt[b[i]]++;
        if(cnt[b[i]] > 1) dfvals.insert(b[i]);
    }

    int ans = 0;
    vector<vector<int> > pre(n+1, vector<int>(3)), suf(n+1, vector<int>(3)); // 0 => max < itr, 1 => max = itr, 2 => max > itr
    for(auto itr: dfvals){
        pre[0][0] = 1;
        pre[0][1] = pre[0][2] = 0;

        for(int i = 0; i < n; i++){
            pre[i+1][0] = pre[i+1][1] = pre[i+1][2] = 0;
            
            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;
        suf[n][1] = suf[n][2] = 0;

        for(int i = n-1; i >= 0; i--){
            suf[i][0] = suf[i][1] = suf[i][2] = 0;

            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;
}

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