Submission #930379

#	Time	Username	Problem	Language	Result	Execution time	Memory
930379		haxorman	Fancy Fence (CEOI20_fancyfence)	C++14	100 / 100	66 ms	12232 KiB

fancyfence

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

#define int long long

const int mxN = 1e5 + 7;
const int SZ = exp2(ceil(log2(mxN)));
const int MOD = 1e9 + 7;

int pref[mxN], nex[mxN], prv[mxN], seg[4 * mxN], lazy[4 * mxN];
pair<int,int> arr[mxN];

void push(int ind, int l, int r) {
    if (lazy[ind]) {
        seg[ind] = (r - l + 1) * lazy[ind] % MOD;
        if (l != r) {
            lazy[2*ind] = lazy[ind];
            lazy[2*ind+1] = lazy[ind];
        }
        lazy[ind] = 0;
    }
}

void update(int lo, int hi, int val, int ind = 1, int l = 0, int r = SZ - 1) {
    push(ind, l, r);
    if (lo > r || l > hi) {
        return;
    }

    if (lo <= l && r <= hi) {
        lazy[ind] = val;
        push(ind, l, r);
        return;
    }

    int mid = (l + r) / 2;
    update(lo, hi, val, 2*ind, l, mid);
    update(lo, hi, val, 2*ind+1, mid+1, r);
}

int query(int pos, int ind = 1, int l = 0, int r = SZ - 1) {
    push(ind, l, r);
    if (l == r) {
        return seg[ind];
    }

    int mid = (l + r) / 2;
    if (pos <= mid) {
        return query(pos, 2*ind, l, mid);
    }
    else {
        return query(pos, 2*ind+1, mid+1, r);
    }
}

int nc2(int n) {
    return n * (n - 1) / 2;
}

int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    int n;
    cin >> n;
    
    vector<pair<int,int>> pos;
    for (int i = 1; i <= n; ++i) {
        cin >> arr[i].first;
        pos.push_back({arr[i].first, i});
    }
    sort(pos.begin(), pos.end());

    for (int i = 1; i <= n; ++i) {
        cin >> arr[i].second;
        pref[i] = pref[i - 1] + arr[i].second;
    }
    
    vector<int> st = {n + 1};
    for (int i = n; i >= 1; --i) {
        while (st.size() && arr[i].first <= arr[st.back()].first) {
            st.pop_back();
        }
        assert(st.size());
        nex[i] = st.back();
        st.push_back(i);
    }
    
    st = {0};
    for (int i = 1; i <= n; ++i) {
        while (st.size() && arr[i].first <= arr[st.back()].first) {
            st.pop_back();
        }
        assert(st.size());
        prv[i] = st.back();
        st.push_back(i);
    }

    int ans = 0;
    for (auto [h, i] : pos) {
        int w = (pref[nex[i] - 1] - pref[prv[i]]) % MOD;

        ans += (nc2(h + 1) - query(i)) % MOD * (nc2(w + 1) % MOD) % MOD;
        ans %= MOD;

        update(prv[i] + 1, nex[i] - 1, nc2(h + 1) % MOD);
    }
    cout << ans << "\n";
}

Compilation message (stderr)

fancyfence.cpp: In function 'int32_t main()':
fancyfence.cpp:99:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   99 |     for (auto [h, i] : pos) {
      |               ^

• Subtask 1: 0 / 0
• Subtask 2: 12 / 12
• Subtask 3: 13 / 13
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 18 / 18
• Subtask 7: 27 / 27