Submission #465837

#	Time	Username	Problem	Language	Result	Execution time	Memory
465837		ivan_tudor	Fancy Fence (CEOI20_fancyfence)	C++14	100 / 100	78 ms	5316 KiB

fancyfence

#include<bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7;
const unsigned long long N = 1e5+5;
unsigned long long lgcput(unsigned long long b,unsigned long long p){
  unsigned long long a = 1;
  while(p){
    if(p & 1){
      a *= b;
      a%=MOD;
    }
    b*=b;
    b%=MOD;
    p/=2;
  }
  return a;
}
unsigned long long cost(unsigned long long n){
  return ((unsigned long long)(((unsigned long long)(n *(n+1)))%MOD) *(lgcput(2,MOD-2) % MOD)) %MOD ;
}
struct drept{
  unsigned long long h,w;
};
drept v[N];
unsigned long long stk[N];
 
unsigned long long nwc[N];
int main()
{
  //freopen(".in","r",stdin);
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  unsigned long long n;
  cin>>n;
  for(unsigned long long i =1;i<=n;i++){
    cin>>v[i].h;
  }
  for(unsigned long long i=1;i<=n;i++){
    cin>>v[i].w;
  }
  unsigned long long ans = 0;
  unsigned long long nw = 0;
  unsigned long long vf = 0;
  nwc[0] = 0;
  for(unsigned long long i=1;i<=n;i++){
    unsigned long long dlted = 0;
    while(vf>0 && v[stk[vf]].h >= v[i].h){
      dlted += v[stk[vf]].w;
      dlted %= MOD;
      v[i].w %=MOD;
      vf--;
    }
    nw = ((unsigned long long)nwc[stk[vf]] + ((unsigned long long)cost(v[i].h) * dlted)%MOD ) %MOD;
    ans += ((unsigned long long) nw * v[i].w)%MOD;
    ans %= MOD;
    ans += ((unsigned long long)cost(v[i].h) * cost(v[i].w)) % MOD;
    ans %= MOD;
    nw  += ((unsigned long long) cost(v[i].h) * v[i].w) % MOD;
    nw %= MOD;
    nwc[i] = nw;
    stk[++vf] = i;
    v[i].w += dlted;
    v[i].w%=MOD;
  }
  cout<<ans;
  return 0;
}

• 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