제출 #1218792

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1218792		BigBadBully	Flooding Wall (BOI24_wall)	C++20	25 / 100	5083 ms	24508 KiB

Main

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

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