oj.uz

Submission #881497

# Submission time Handle Problem Language Result Execution time Memory
881497 2023-12-01T10:01:51 Z Iliya_ Fancy Fence (CEOI20_fancyfence) C++17
0 / 100
 1 ms 2648 KB 
//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 fastio      ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
typedef long long ll; 
typedef long double dll;

#define int long long 
const int N = 1e5+7, mod = 1e9+7;
int dp[N], h[N], w[N], sum[N]; 
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;
}

int32_t main(){
     fastio;

     vec.pb({1e9+1,0}); 
     dp[0] = 0; 
     int 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];
          sum[i] = (sum[i-1] + w[i]) % mod;
     }
     for(int i=1; i<=n; i++){
          while(vec.size() && vec.back().F >= h[i]) vec.pop_back();
          int majw = (vec.size() ? sum[i] - sum[vec.back().S] : sum[i]); 
          dp[i] = w[i] * (vec.size() ? dp[vec.back().S] : 0); 
          vec.pb({h[i],i}); 
          int ravh = (h[i] + 1) * h[i] * inv2 % mod;
          ravh %= mod; 
          int en = majw, st = majw - h[i] + 1; 
          int ravw = (st+en) * (en-st+1) * inv2 % mod; 
          ravw %= mod; 
          dp[i] = (dp[i] + ravw * ravh % mod) % mod; 
     }
     int ans = 0; 
     for(int i=1; i<=n; i++) ans = (ans + dp[i]) % mod; 
     cout << ans << endl;

     return 0;
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Incorrect 1 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Incorrect 1 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Incorrect 1 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Incorrect 1 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Incorrect 1 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -