제출 #1274652

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1274652		icebear	Flooding Wall (BOI24_wall)	C++20	100 / 100	1666 ms	135448 KiB

Main

// ~~ icebear ~~
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;

template<class T>
    bool minimize(T &a, const T &b) {
        if (a > b) return a = b, true;
        return false;
    }

template<class T>
    bool maximize(T &a, const T &b) {
        if (a < b) return a = b, true;
        return false;
    }

#define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
#define FORR(i,a,b) for(int i=(a); i>=(b); --i)
#define REP(i, n) for(int i=0; i<(n); ++i)
#define RED(i, n) for(int i=(n)-1; i>=0; --i)
#define MASK(i) (1LL << (i))
#define BIT(S, i) (((S) >> (i)) & 1)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define task "icebear"

const int MOD = 1e9 + 7;
const int inf = 1e9 + 27092008;
const ll INF = 1e18 + 27092008;
const int N = 5e5 + 5;
int n, a[N], b[N], power2[N];
vector<int> pos[2 * N];
// ans = sum((2^(i-1) - pref[i-1]) * (2^(n-i) - suff[i+1]) * way[i]) * (h[x] - h[x-1])
// ans = sum((2^(n-1) * w[i] - 2^(i-1) * s[i] - 2^(n-i) * p[i] + p[i] * s[i+1]) * (h[x] - h[x-1]))

struct calcSuff { // 2^(i-1) * s[i]
    int len, ans, suf;
    calcSuff(): len(1), ans(0), suf(0) {}

    void update() {
        ans++;
        suf++;
    }

    friend calcSuff combine(const calcSuff &L, const calcSuff &R) {
        calcSuff res;
        res.len = L.len + R.len;
        res.ans = (1LL * L.ans * R.suf + 1LL * power2[L.len] * R.ans) % MOD;
        res.suf = 1LL * L.suf * R.suf % MOD;
        return res;
    }
};

struct calcPref { // 2^(n-i) * p[i]
    int len, ans, pre;
    calcPref(): len(1), ans(0), pre(0) {}

    void update() {
        ans++;
        pre++;
    }

    friend calcPref combine(const calcPref &L, const calcPref &R) {
        calcPref res;
        res.len = L.len + R.len;
        res.ans = (1LL * R.ans * L.pre + 1LL * power2[R.len] * L.ans) % MOD;
        res.pre = 1LL * L.pre * R.pre % MOD;
        return res;
    }
};

struct calcMult { // p[i] * s[i + 1]
    int ans, pre, suf;
    calcMult(): ans(0), pre(0), suf(0) {}

    void update() {
        ans++;
        pre++;
        suf++;
    }

    friend calcMult combine(const calcMult &L, const calcMult &R) {
        calcMult res;
        res.ans = (1LL * L.ans * R.suf + 1LL * R.ans * L.pre) % MOD;
        res.pre = 1LL * L.pre * R.pre % MOD;
        res.suf = 1LL * L.suf * R.suf % MOD;
        return res;
    }
};

template<class T>
    struct SegmentTree {
        vector<T> node;

        void build(int id, int l, int r) {
            if (l == r) {
                node[id] = T();
                return;
            }
            int mid = (l + r) >> 1;
            build(id << 1, l, mid);
            build(id << 1 | 1, mid + 1, r);
            node[id] = combine(node[id << 1], node[id << 1 | 1]);
        }

        SegmentTree(int _n = 0):
            node(4 * n + 5) {
                build(1, 1, n);
            }

        void update(int pos) {
            int id = 1, l = 1, r = n;
            while(l < r) {
                int mid = (l + r) >> 1;
                if (pos > mid) id = (id << 1 | 1), l = mid + 1;
                else id = (id << 1), r = mid;
            }
            node[id].update();
            while(id > 1) {
                id >>= 1;
                node[id] = combine(node[id << 1], node[id << 1 | 1]);
            }
        }

        int get_ans() {
            return node[1].ans;
        }
    };

void init(void) {
    cin >> n;
    FOR(i, 1, n) cin >> a[i];
    FOR(i, 1, n) cin >> b[i];
}

void process(void) {
    power2[0] = 1;
    FOR(i, 1, n) power2[i] = 1LL * power2[i - 1] * 2 % MOD;

    vector<int> vals(1, 0);
    FOR(i, 1, n) {
        vals.pb(a[i]);
        vals.pb(b[i]);
    }
    sort(all(vals));
    vals.resize(unique(all(vals)) - vals.begin());

    FOR(i, 1, n) {
        int p1 = lower_bound(all(vals), a[i]) - vals.begin();
        int p2 = lower_bound(all(vals), b[i]) - vals.begin();
        pos[p1].pb(i);
        pos[p2].pb(i);
    }

    int ans = 0;
    SegmentTree<calcSuff> it_suff(n);
    SegmentTree<calcPref> it_pref(n);
    SegmentTree<calcMult> it_mult(n);

    FOR(i, 1, (int)vals.size() - 1) {
        int diff = vals[i] - vals[i - 1];
        ans = (ans - 1LL * it_suff.get_ans() * diff % MOD + MOD) % MOD;
        ans = (ans - 1LL * it_pref.get_ans() * diff % MOD + MOD) % MOD;
        ans = (ans + 1LL * it_mult.get_ans() * diff % MOD + MOD) % MOD;
        for(int &p : pos[i]) {
            it_suff.update(p);
            it_pref.update(p);
            it_mult.update(p);
        }
    }

    FOR(i, 1, n) {
        ans = (ans + 1LL * power2[n - 1] * (vals.back() - a[i]) % MOD) % MOD;
        ans = (ans + 1LL * power2[n - 1] * (vals.back() - b[i]) % MOD) % MOD;
    }

    cout << ans;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    if (fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    int tc = 1;
//    cin >> tc;
    while(tc--) {
        init();
        process();
    }
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'int main()':
Main.cpp:191:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  191 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:192:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  192 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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