Submission #1218792

#TimeUsernameProblemLanguageResultExecution timeMemory
1218792BigBadBullyFlooding Wall (BOI24_wall)C++20
25 / 100
5083 ms24508 KiB
#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define ff first
#define ss second
const int mod = 1e9 + 7;
const int maxn = 1e6;

using namespace std;
vector<int> dva(maxn + 1, 1);
void init()
{
    for (int i = 1; i <= maxn; i++)
        dva[i] = dva[i - 1] * 2 % mod;
}

signed main()
{
    init();
    int n;
    cin >> n;
    vector<pii> v(n);
    for (pii &x : v)
        cin >> x.ff;
    for (pii &x : v)
        cin >> x.ss;
    for (pii &x : v)
        if (x.ff > x.ss)
            swap(x.ff, x.ss);
    vector<int> alles;
    for (pii &x : v)
        alles.push_back(x.ff), alles.push_back(x.ss);
    sort(alles.begin(), alles.end());
    alles.resize(unique(alles.begin(), alles.end()) - alles.begin());
    for (pii &x : v)
        x.ff = lower_bound(alles.begin(), alles.end(), x.ff) - alles.begin(),
        x.ss = lower_bound(alles.begin(), alles.end(), x.ss) - alles.begin();
    int dst = alles.size();
    auto f = [&](int idx, int num,bool vrst) -> int
    {
        int m = 0, x = 0, y = 0;
        int res = 1;
        bool typ = 0;

        for (int i = 0; i < idx; i++)
        {
            if (v[i].ff > num)
                return 0;
            if (v[i].ss > num)
            {
                if (v[i].ff == num)
                    typ = 1;
                continue;
            }
                
            if (v[i].ss < num)
                m++;
            if (v[i].ss == num)
                x++;
        }
        res = dva[m] * (typ ? dva[x] : (dva[x] - 1 + mod)) % mod;
        for (int i = idx + 1; i < n; i++)
        {
            if (v[i].ff >= num+vrst)
                return res * dva[n - idx - 1] % mod;
            if (v[i].ss < num+vrst)
                m++;
            if (v[i].ss >= num+vrst)
                y++;
        }
        return dva[m] * (typ ? dva[x] : (dva[x] - 1 + mod)) % mod * 
                (dva[y] - 1 + mod) % mod;
    };

    int ans = 0;
    for (int it = 0; it < 2; it++)
    {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < dst; j++)
                ans += max(0ll, (alles[j] - alles[v[i].ff]) * f(i, j,it)%mod),
                    ans += max(0ll, (alles[j] - alles[v[i].ss]) * f(i, j,it)%mod);
        reverse(v.begin(), v.end());
    }
    cout << ans%mod << '\n';
}
#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...