Submission #922628

#	Time	Username	Problem	Language	Result	Execution time	Memory
922628		BigBadBully	Fancy Fence (CEOI20_fancyfence)	C++17	30 / 100	24 ms	4724 KiB

fancyfence

#include<bits/stdc++.h>
#define int long long
#define ff first
#define ss second
using namespace std;
const int mod = 1'000'000'000 + 7;
struct seg{
    int l,r,h;
    
};
bool operator<(const seg& a, const seg& b){
    return a.l < b.l;
};
bool operator>(const seg& a, const seg& b){
    return a.l < b.l;
};

int sum (int l,int r)
{
    
    return ((r*r+r)/2 - (l*l-l)/2)%mod;
}

const int dva = 500000004LL;

void solve()
{

    int n;
    cin >> n;
    int at = 0;
    vector<seg> v(n);
    for (int i = 0; i<n; i++)
    {
        int aew;
        cin >> aew;
        v[i].h = aew;
    }
    for (int i = 0; i < n; i++)
    {
        int w;
        cin >> w;
        v[i].l = at;
        v[i].r = at+w-1;
        at=v[i].r+1;
    }
    int ans = 0;
    int cur = 0;
    set<pair<int,int>> cat;
    
    
    cat.insert({v[0].l,v[n-1].r});
    

    auto remove = [&](seg x)
    {
        pair<int,int> big = *(--cat.upper_bound({x.l,x.r}));
      
        int biglen = big.ss-big.ff+1;
        int oduz =(int)((((__uint128_t)biglen)*((__uint128_t)biglen)+((__uint128_t)biglen))/((__uint128_t)2)%mod);
        cur-=oduz;
        cur+=7*mod;
        cur%=mod;

        if (x.l-1 >= big.ff)
            cat.insert({big.ff,x.l-1});
        if (x.r+1 <= big.ss)
            cat.insert({x.r+1,big.ss});
        

        int len1 = max(0LL,(x.l-1 - big.ff)+1);
        int len2 = max(0LL,big.ss - x.r);
        int oduz1 =(int)((((__uint128_t)len1)*((__uint128_t)len1)+((__uint128_t)len1))/((__uint128_t)2)%mod);
        int oduz2 =(int)((((__uint128_t)len2)*((__uint128_t)len2)+((__uint128_t)len2))/((__uint128_t)2)%mod);

        cat.erase(--cat.upper_bound({x.l,x.r}));
        cur+=oduz1+oduz2;
        cur%=mod;
    };
    auto comp = [&](seg& mile, seg& alen){
        return (mile.h < alen.h);
    };
    int globallen = (v[n-1].r - v[0].l + 1);
    sort(v.begin(),v.end(),comp);
    int prev = 0;
    int same = 0;
    
    globallen%=mod;
    cur = globallen*globallen+globallen;
    cur%=mod;
    cur*=dva;
    cur%=mod;

    for (int i = 0; i < n; i++)
    {
       
        
        
        if (i!=0 && v[i].h != v[i-1].h)
        {
            ans+=(cur*(sum(prev+1,v[i-1].h)))%mod;
            ans%=mod;
            for (int j = i-1; j >= same; j--)
                remove(v[j]);
            
            same = i;
            prev = v[i-1].h;
        }
    }

    ans+=(cur*(sum(prev+1,v[n-1].h)))%mod;
    ans%=mod;

    cout << ans << '\n';
    return;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //freopen("input1.txt", "r", stdin);
    solve();
    
}

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