Submission #1173219

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173219		danglayloi1	Fancy Fence (CEOI20_fancyfence)	C++20	100 / 100	128 ms	15572 KiB

fancyfence

#include <bits/stdc++.h>
#define ii pair<int, int>
#define fi first
#define se second
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
using ll = long long;
const ll mod=1e9+7;
const int nx=1e5+5;
ll add(ll a, ll b)
{
    a+=b;
    if(a>=mod) a-=mod;
    return a;
}
ll mul(ll a, ll b)
{
    a*=b;
    if(a>=mod) a%=mod;
    return a;
}
ll del(ll a, ll b)
{
    a-=b;
    if(a<0) a+=mod;
    return a;
}
ll pw(ll a, ll n)
{
    if(!n) return 1;
    ll tmp=pw(a, n>>1);
    tmp=mul(tmp, tmp);
    if(n&1) tmp=mul(tmp, a);
    return tmp;
}
ll base;
ll get(ll l, ll r)
{
    return mul(mul(add(l, r), (r-l+1+mod)%mod), base);
}
int n, r[nx];
pair<ll, ll> seg[nx];
ll h[nx], w[nx], ans=0, cur=0;
vector<int> rar, st[nx];
map<ll, ll> mp;
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    base=pw(2, mod-2);
    cin>>n;
    for(int i = 1; i <= n; i++)
        cin>>h[i], rar.emplace_back(h[i]);
    for(int i = 1; i <= n; i++)
    {
        cin>>w[i];
        seg[i]={cur+1, cur+w[i]};
        cur+=w[i];
    }
    cur=0;
    sort(rar.begin(), rar.end());
    rar.erase(unique(rar.begin(), rar.end()), rar.end());
    for(int i = 1; i <= n; i++)
        h[i]=upper_bound(rar.begin(), rar.end(), h[i])-rar.begin(), st[h[i]].emplace_back(i);
    for(int i = rar.size(); i >= 1; i--)
    {
        for(int id:st[i])
        {
            ll le=seg[id].fi, ri=seg[id].se;
            if(mp.find(le-1)!=mp.end())
            {
                cur=del(cur, get(1, (le-mp[le-1])%mod));
                le=mp[le-1];
            }
            if(mp.find(ri+1)!=mp.end())
            {
                cur=del(cur, get(1, (mp[ri+1]-ri)%mod));
                ri=mp[ri+1];
            }
            mp[le]=ri;
            mp[ri]=le;
            cur=add(cur, get(1, (ri-le+1)%mod));
        }
        ll hei=(i==1)?rar[0]:(rar[i-1]-rar[i-2]);
        ans=add(ans, mul(cur, get(del(rar[i-1], hei-1), rar[i-1])));
    }
    cout<<ans;
}

• 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