Submission #881603

#	Time	Username	Problem	Language	Result	Execution time	Memory
881603		Iliya_	Fancy Fence (CEOI20_fancyfence)	C++17	100 / 100	21 ms	7336 KiB

fancyfence

//IN THE NAME OF GOD
#include<bits/stdc++.h>
#pragma GCC optimize("O2,unroll-loops")
#define endl        '\n'
#define F           first
#define S           second
#define pii         pair<int,int>
#define all(x)      x.begin(),x.end()
#define pb          push_back
#define fast_io     ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define file_io     freopen("input.in" , "r" , stdin) ; freopen("output.out" , "w" , stdout);
using namespace std;
typedef long long ll; 
typedef long double dll;

#define int long long
const int N = 1e5+7, mod = 1e9+7;
int h[N], w[N], sumw[N], dp[N], ans[N], inv2; 
vector<pii> vec; 

int power(int a, int b){
     int ans = 1;
     while(b){
          if (b&1) ans = ans * a % mod; 
          a = a * a % mod; 
          b /= 2; 
     }
     return ans; 
}

int f(int x){
     return (x * (x-1) % mod * inv2 % mod);
}

int32_t main(){
     fast_io; 

     inv2 = power(2,mod-2); 
     int n; cin >> n; 
     for(int i=1; i<=n; i++) cin >> h[i]; 
     for(int i=1; i<=n; i++){
          cin >> w[i]; 
          sumw[i] = (sumw[i-1] + w[i]) % mod; 
     }
     dp[0] = ans[0] = 0;
     vec.pb({0,0}); 
     for(int i=1; i<=n; i++){
          while(vec.back().F >= h[i]) vec.pop_back();
          int ind = vec.back().S;
          vec.pb({h[i],i}); 
          int majw = (sumw[i-1] - sumw[ind] + mod) % mod, majw2 = (sumw[i] - sumw[ind] + mod)%mod;   
          dp[i] = (dp[ind] + f(h[i]+1) * majw2 % mod) %mod;
          ans[i] = (dp[ind] * w[i] % mod + f(h[i]+1) * f(w[i]+1) % mod + f(h[i]+1) * w[i] % mod * majw % mod)%mod; 
     }
     int out = 0; 
     for(int i=1; i<=n; i++) out = (out + ans[i]) % mod; 
     cout << out << endl;

     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