제출 #1085846

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1085846		jerzyk	Flooding Wall (BOI24_wall)	C++17	56 / 100	3164 ms	69504 KiB

Main

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
using namespace __gnu_pbds;
using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const ll M = 1000LL * 1000LL * 1000LL + 7LL;
const int N = 1<<20;
int tab[N][2], rev[N];
ll il[N][2];
bool zer[2 * N];
ll drz[2 * N], drzs[2 * N], laz[2 * N];
ll p2[N];

void Sk(int n)
{
    vector<pair<ll, int>> v;
    for(int i = 1; i <= n; ++i)
    {
        v.pb(make_pair(tab[i][0], i));
        v.pb(make_pair(tab[i][1], i));
    }
    sort(v.begin(), v.end());
    int l = 0;
    for(int i = 0; i < 2 * n; ++i)
    {
        if(i == 0 || v[i].st != v[i - 1].st) ++l;
        rev[l] = v[i].st;
        if(tab[v[i].nd][0] == v[i].st) tab[v[i].nd][0] = l;
        if(tab[v[i].nd][1] == v[i].st) tab[v[i].nd][1] = l;
    }
}

void P2(int n)
{
    p2[0] = 1LL;
    for(int i = 1; i <= n; ++i)
        p2[i] = (p2[i - 1] * 2LL) % M;
}

inline void Clean()
{
    for(int i = 1; i < 2 * N; ++i)
    {
        drz[i] = 0LL; drzs[i] = 0LL;
        laz[i] = 1LL;
        zer[i] = false;
    }
}

inline void Push(int v)
{
    if(zer[v])
    {
        zer[v * 2] = true;
        zer[v * 2 + 1] = true;
        return;
    }
    for(int s = v * 2; s <= v * 2 + 1; ++s)
    {
        drz[s] = (drz[s] * laz[v]) % M;
        drzs[s] = (drzs[s] * laz[v]) % M;
        laz[s] = (laz[s] * laz[v]) % M;
    }
    laz[v] = 1LL;
}

inline void Upd(int v)
{
    if(zer[v])
        return;
    drz[v] = ((drz[v * 2] + drz[v * 2 + 1]) * laz[v]) % M;
    drzs[v] = ((drzs[v * 2] + drzs[v * 2 + 1]) * laz[v]) % M;
}

void Zeruj(int v, int p, int k, int pz, int kz)
{
    if(pz > kz) return;
    if(zer[v]) return;
    if(p > kz || k < pz) return;
    if(p >= pz && k <= kz)
    {
        drz[v] = 0LL; drzs[v] = 0LL;
        laz[v] = 0LL;
        zer[v] = true;
        return;
    }
    Zeruj(v * 2, p, (p + k) / 2, pz, kz);
    Zeruj(v * 2 + 1, (p + k) / 2 + 1, k, pz, kz);
    Upd(v);
}

void Dod(int v, ll x)
{
    v += N;
    if(zer[v]) return;
    int sv = v;
    v /= 2;
    vector<int> xd;
    while(v > 0)
        {xd.pb(v); v /= 2;}
    for(int i = (int)xd.size() - 1; i >= 0; --i)
        Push(xd[i]);
    if(zer[v]) return;
    v = sv;
    drz[v] += x;
    drzs[v] += x * (ll)rev[(v - N)];
    drz[v] %= M; drzs[v] %= M;
    v /= 2;
    while(v > 0)
        {Upd(v); v /= 2;}
}

void Mn2(int v, int p, int k, int pz, int kz)
{
    if(p > kz || k < pz || zer[v]) return;
    if(p >= pz && k <= kz)
    {
        drz[v] = (drz[v] * 2LL) % M;
        drzs[v] = (drzs[v] * 2LL) % M;
        laz[v] = (laz[v] * 2LL) % M;
        return;
    }
    Mn2(v * 2, p, (p + k) / 2, pz, kz);
    Mn2(v * 2 + 1, (p + k) / 2 + 1, k, pz, kz);
    Upd(v);
}

pair<ll, ll> Sum(int v, int p, int k, int pz, int kz)
{
    if(p > kz || k < pz || zer[v]) return make_pair(0LL, 0LL);
    if(p >= pz && k <= kz)
        return make_pair(drz[v], drzs[v]);
    pair<ll, ll> a, b;
    a = Sum(v * 2, p, (p + k) / 2, pz, kz);
    b = Sum(v * 2 + 1, (p + k) / 2 + 1, k, pz, kz);
    a = make_pair((a.st + b.st) * laz[v], (a.nd + b.nd) * laz[v]);
    //if(kz == 1)
        //cout << "Sum: " << v << " " << a.nd << "\n";
    a.st %= M; a.nd %= M;
    return a;
}

ll LR(int n)
{
    Clean();
    ll ans = 0LL;
    Dod(tab[1][0], 1LL);
    Dod(tab[1][1], 1LL);
    il[1][0] = 1LL;
    il[1][1] = 1LL;
    for(int i = 2; i <= n; ++i)
    {
        pair<ll, ll> s1, s2;
        ll a = rev[tab[i][0]], b = rev[tab[i][1]];

        s1 = Sum(1, 0, N - 1, 0, tab[i][0] - 1);
        s2 = Sum(1, 0, N - 1, 0, tab[i][1] - 1);

        //cout << "LR: " << s1.st << " " << s2.st << "\n";

        Zeruj(1, 0, N - 1, 0, tab[i][0] - 1);
        Mn2(1, 0, N - 1, tab[i][1], N - 1);

        ans += (((((a * s1.st - s1.nd) % M) * (ll)(i - 1)) % M) * p2[n - i]) % M;
        ans += (((((b * s2.st - s2.nd) % M) * (ll)(i - 1)) % M) * p2[n - i]) % M;
        ans %= M;

        il[i][0] = s1.st;
        il[i][1] = s2.st;

        Dod(tab[i][0], s1.st);
        Dod(tab[i][1], s2.st);
    }
    //cout << ans << "\n";
    ans %= M;
    ans += M;
    ans %= M;
    return ans;
}

ll RL(int n)
{
    ll ans = 0LL;
    Clean();
    Dod(tab[n][0], 1LL);
    Dod(tab[n][1], 1LL);
    for(int i = n - 1; i >= 1; --i)
    {
        pair<ll, ll> s1, s2;
        ll a = rev[tab[i][0]], b = rev[tab[i][1]];

        s1 = Sum(1, 0, N - 1, 0, tab[i][0] - 1);
        s2 = Sum(1, 0, N - 1, 0, tab[i][1] - 1);

        //cout << drz[N / 2] << " " << "LR: " << s1.nd << " " << s2.nd << "\n";

        il[i][0] *= Sum(1, 0, N - 1, 0, tab[i][0]).st;
        il[i][1] *= Sum(1, 0, N - 1, 0, tab[i][1]).st;
        il[i][0] %= M; il[i][1] %= M;


        Zeruj(1, 0, N - 1, 0, tab[i][0] - 1);
        Mn2(1, 0, N - 1, tab[i][1], N - 1);

        ans += (((a * s1.st - s1.nd) * (ll)(n - i)) % M) * p2[i - 1];
        ans += (((b * s2.st - s2.nd) * (ll)(n - i)) % M) * p2[i - 1];
        ans %= M;



        Dod(tab[i][0], s1.st);
        Dod(tab[i][1], s2.st);
    }

    //for(int i = 1; i <= n; ++i)
        //cout << "IL: " << il[i][0] << " " << il[i][1] << "\n";

    //cout << ans << "\n";

    ans %= M;
    ans += M;
    ans %= M;
    return ans;
}

void Solve()
{
    int n;
    ll ans = 0LL, s = 0LL;
    cin >> n;
    P2(n);
    for(int r = 0; r < 2; ++r)
        for(int i = 1; i <= n; ++i)
        {
            cin >> tab[i][r];
            s += (tab[i][r] * p2[n - 1]) % M;
        }
    s %= M;
    for(int i = 1; i <= n; ++i)
        if(tab[i][0] > tab[i][1]) swap(tab[i][0], tab[i][1]);
    Sk(n);
    //cout << "S: " << s << "\n";
    s += LR(n);
    s += RL(n);
    //cout << "S: " << s << "\n";
    s %= M;
    for(int i = 1; i <= n; ++i)
    {
        ans += il[i][0] * rev[tab[i][0]];
        ans += il[i][1] * rev[tab[i][1]];
        ans %= M;
    }
    //cout << "sp: " << ans << "\n";
    ans *= (ll)n;
    ans %= M;
    ans = (ans - s + M) % M;
    cout << ans << "\n";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //int t; cin >> t;
    //while(t--)
        Solve();

    return 0;
}

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