제출 #1219200

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1219200		BigBadBully	Flooding Wall (BOI24_wall)	C++20	70 / 100	5094 ms	55272 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++)
    {
        int mini = v[0].ff;
        vector<pii> pref(dst,{0,0});
        vector<pii> suf(dst,{0,0});
        for (pii x:v)suf[x.ff].ff++,suf[x.ss].ss++;
        for (int i = 1; i < dst; i++)
            suf[i].ff+=suf[i-1].ff,suf[i].ss+=suf[i-1].ss;
        auto ssuf = [&](int l,int r)->pii
        {
            if (l>r)return {0,0};
            return {suf[r].ff-(l>0?suf[l-1].ff:0),suf[r].ss-(l>0?suf[l-1].ss:0)};
        };
        auto spref = [&](int l,int r)->pii
        {
            if (l>r)return {0,0};
            return {pref[r].ff-(l>0?pref[l-1].ff:0),pref[r].ss-(l>0?pref[l-1].ss:0)};
        };
        
        for (int i = 0; i < n-1; i++)
        {
            
            mini = max(mini,v[i].ff);
            for (int j = v[i].ff; j < dst; j++)
                suf[j].ff--;
            for (int j = v[i].ss; j < dst; j++)
                suf[j].ss--;
            for (int num = mini+(i==0)*dst; num < dst; num++)
            {
                int m = 0, x = 0, y = 0,res = 0;
                m+=spref(0,num-1).ss;
                x+=spref(num,num).ss;
                if (ssuf(num+it,dst-1).ff)
                    res=dva[m]*(dva[x]-(num!=mini)+mod)%mod*dva[n-i-1]%mod;
                else
                {
                    m+=ssuf(0,num+it-1).ss;
                    y+=ssuf(num+it,dst-1).ss;
                    res=dva[m]*(dva[x]-(num!=mini)+mod)%mod*(dva[y]-1)%mod;
                }
                ans+=max(0ll,(alles[num]-alles[v[i].ff])*res%mod);
                ans+=max(0ll,(alles[num]-alles[v[i].ss])*res%mod);
            }
            for (int j = v[i].ff; j < dst; j++)
                pref[j].ff++;
            for (int j = v[i].ss; j < dst; j++)
                pref[j].ss++;
        }
        reverse(v.begin(), v.end());
    }
    cout << ans % mod << '\n';
}

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