Submission #1358534

#TimeUsernameProblemLanguageResultExecution timeMemory
1358534faricaFlooding Wall (BOI24_wall)C++20
0 / 100
4 ms4164 KiB
#include<bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using pi = pair<int,int>;
typedef long long ll;
#define debug(x) cout << #x << " = " << x << "\n";
#define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n";

const int MOD = 1e9+7;
const int N = 1e6;

vi bin;

void solve() {
    int n;
    cin >> n;
    int a[n], b[n];
    for(int i=0; i<n; ++i) cin >> a[i];
    vi cnt(n), id(n), eq(n);
    vector<pi>vec(n);
    for(int i=0; i<n; ++i) {
        cin >> b[i];
        vec[i] = {b[i], i};
        if(a[i] > b[i]) swap(a[i], b[i]);
    }
    sort(vec.begin(), vec.end());
    int les = 0, sam = 0;
    for(int i=0; i<n; ++i) {
        if(i && vec[i].first != vec[i-1].first) {
            les += sam;
            sam = 0;
        }
        eq[vec[i].second] = sam;
        id[vec[i].second] = les;
        ++sam;
    }
    int ans = 0;
    for(int i=1; i<n-1; ++i) {
        for(int j=i-1; j>=0; --j) {
            if(b[j] <= a[i]) continue;
            if(b[j] > b[i]) --id[j];
            int cur = 0;
            for(int k=i+1; k<n; ++k) {
                if(b[k] < b[j]) continue;
                cur = (cur + 1ll * bin[id[j]+eq[j]+n-1-k]) % MOD;
            }
            if(b[j] > b[i]) ++id[j];
            ans = (ans + 1ll * cur * (b[j] - a[i]) % MOD) % MOD;
            if(b[i] < b[j]) ans = (ans + 1ll * cur * (b[j] - b[i]) % MOD) % MOD;
        }
    }
    cout << ans << endl;
}

int main(){
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	bin.resize(N);
	bin[0] = 1;
	for(int i=1; i<N; ++i) bin[i] = (bin[i-1] * 2) % MOD;

	int tc = 1;
	while(tc--) solve();
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...