Submission #1276249

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276249		abdelhakim	Fancy Fence (CEOI20_fancyfence)	C++20	100 / 100	137 ms	11460 KiB

fancyfence

#include <bits/stdc++.h>
#define ll long long
#define mod (ll)(1e9+7)
#define dbg(x) cerr<<#x<<' '<<x<<endl;
ll two=(mod+1)/2;
using namespace std;
ll maxn=1e5;
vector<pair<ll,ll>> tree(4*maxn+3);
void update(ll node, ll l, ll r, ll pos, ll val)
{
  if(pos < l || pos > r)
  {
    return;
  }
  if(l==r)
  {
    tree[node]={0,val};
    return;
  }
  ll mid=(l+r)>>1;
  update(node*2+1,l,mid,pos,val);
  update(node*2+2,mid+1,r,pos,val);
  tree[node].second=(tree[node*2+1].second+tree[node*2+2].second)%mod;
  tree[node].first=(tree[node*2+2].first+tree[node*2+1].first)%mod+(tree[node*2+1].second*tree[node*2+2].second)%mod;
  tree[node].first%=mod;
}
pair<ll,ll> query(ll node, ll l, ll r, ll x, ll y)
{
  if(max(l,x) > min(y,r)) return {0,0};
  if(x<=l && r<=y)
  {
    return tree[node];
  }
  ll mid=(l+r)>>1;
  pair<ll,ll> qr1=query(node*2+1,l,mid,x,y);
  pair<ll,ll> qr2=query(node*2+2,mid+1,r,x,y);
  return {((qr1.first+qr2.first)%mod+(qr1.second*qr2.second)%mod)%mod,(qr1.second+qr2.second)%mod};
}
int main()
{
  ll n;
  cin>>n;
  vector<ll> h(n);
  vector<ll> w(n);
  for (int i=0;i<n;i++)
  {
    cin>>h[i];
  }
  for (int i=0;i<n;i++)
  {
    cin>>w[i];
  }
  ll ans=0;
  for (int i=0;i<n;i++)
  {
    ll l3iba=h[i]*(h[i]+1)%mod*two%mod;
    ll l3iba2=w[i]*(w[i]+1)%mod*two%mod;
    ans+=l3iba*l3iba2%mod;
    ans%=mod;
  }
  vector<pair<ll,ll>> range(n,{0,n-1});
  stack<pair<ll,ll>> s;
  for (int i=0;i<n;i++)
  {
    while(!s.empty() && s.top().first > h[i])
    {
      s.pop();
    }
    if(!s.empty())
    {
      range[i].first=s.top().second+1;
    }
    s.push({h[i],i});
  }
  while(!s.empty()) s.pop();
  for (int i=n-1;i>=0;i--)
  {
    while(!s.empty() && s.top().first >= h[i])
    {
      s.pop();
    }
    if(!s.empty())
    {
      range[i].second=s.top().second-1;
    }
    s.push({h[i],i});
  }
  for (int i=0;i<n;i++)
  {
    update(0,0,n-1,i,w[i]);
  }
  for (int i=0;i<n;i++)
  {
    if(range[i].first==range[i].second)continue;
    ll l3iba=h[i]*(h[i]+1)%mod*two%mod;
    ll qr=(query(0,0,n-1,i,range[i].second).second*query(0,0,n-1,range[i].first,i).second%mod-(w[i]*w[i]%mod)+mod)% mod;
    ans+=(l3iba*qr)%mod;
    ans%=mod;
  }
  cout << ans << endl;
}

• 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