Submission #791380

#	Time	Username	Problem	Language	Result	Execution time	Memory
791380		peteza	Fancy Fence (CEOI20_fancyfence)	C++14	0 / 100	6 ms	9756 KiB

fancyfence

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll mod = 1e9+7;

int n;
ll h[100005], w[100005];
stack<pair<int, ll>> stk;
ll cans = 0;
vector<int> heights;
struct dat {
    ll len = 0, sum = 0, laz = 0;
    dat(){}
    dat(int x){
        sum = laz = 0;
        if(x == 0){
            len = heights[0];
        } else {
            len = heights[x]-heights[x-1];
        }
    }

} segm[400005];

void build(int idx, int l, int r) {
    if(l==r) {
        segm[idx] = dat(l);
        return;
    }
    int mid = (l+r) >> 1;
    build(idx*2+1, l, mid); build(idx*2+2, mid+1, r);
    segm[idx].len = segm[idx*2+1].len + segm[idx*2+2].len;
}

void upd(ll&x){
    if(x < 0) x += mod;
    if(x >= mod) x -= mod;
}

void updlaz(int x, ll val) {
    segm[x].laz += val;
    upd(segm[x].laz);
}

void push(int x) {
    segm[x].sum += segm[x].laz*segm[x].len%mod;
    upd(segm[x].sum);
    if(x*2+2 < 400000) {
        segm[x*2+1].laz += segm[x].laz;
        segm[x*2+2].laz += segm[x].laz;
        upd(segm[x*2+1].laz); upd(segm[x*2+2].laz);
    }
    segm[x].laz = 0;
}

void upd(int idx, int l, int r, int tl, int tr, int val) {
    push(idx);
    if(tl <= l && r <= tr) {
        segm[idx].laz += val;
        upd(segm[idx].laz);
        push(idx);
        return ;
    } else if(tr < l || r < tl) {
        return;
    }
    int mid = (l+r) >> 1;
    upd(idx*2+1, l, mid, tl, tr, val); upd(idx*2+2, mid+1, r, tl, tr, val);
    segm[idx].sum = segm[idx*2+1].sum + segm[idx*2+2].sum;
    //cout << "Updating " << tl << ' ' << tr << " with " << val << '\n';
    //cout << l << ' ' << r << " -> " << segm[idx].sum << '\n';
    upd(segm[idx].sum);
}

ll qr(int idx, int l, int r, int tl, int tr) {
    push(idx);
    if(tl <= l && r <= tr) return segm[idx].sum;
    if(tr < l || r < tl) return 0;
    int mid = (l+r) >> 1;
    ll res = qr(idx*2+1, l, mid, tl, tr) + qr(idx*2+2, mid+1, r, tl, tr);
    if(res >= mod) res -= mod;
    return res;
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    cin >> n;
    heights.push_back(1);
    for(int i=0;i<n;i++) cin >> h[i], heights.push_back(h[i]);
    for(int i=0;i<n;i++) cin >> w[i];
    sort(heights.begin(), heights.end());
    heights.resize(unique(heights.begin(), heights.end())-heights.begin());
    int hs = heights.size()-1;
    build(0, 0, hs);
    for(int i=0;i<n;i++) {
        ll cw = w[i];
        cans += (((h[i]*(h[i]+1))/2)%mod*((w[i]*(w[i]+1)/2)%mod))%mod;
        cans += qr(0, 0, hs, 0, lower_bound(heights.begin(), heights.end(), h[i]) - heights.begin())*w[i]%mod;
        upd(cans);
        while(!stk.empty() && stk.top().first >= h[i]) {
            cw += stk.top().second; upd(cw);
            //erase from data structure 1-h with w
            upd(0, 0, hs, 0, lower_bound(heights.begin(), heights.end(), stk.top().first) - heights.begin(), -stk.top().second);
            stk.pop();
        }
        stk.emplace(h[i], cw);
        upd(0, 0, hs, 0, lower_bound(heights.begin(), heights.end(), h[i]) - heights.begin(), cw);

    }
    cout << cans;
}

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