#include <iostream>
#include <vector>
#include <limits>
#define int long long
using namespace std;
int module = 1e9+7;
int fastpow(int b, int e){
int res = 1;
for(;e;e>>=1){
if(e&1) res *= b;
b *= b;
res %= module; b %= module;
}
return res;
}
struct segtree{
vector<pair<int, int>> cache;
segtree(int n){
cache = vector<pair<int, int>> (n*4);
}
pair<int, int> build(int l, int r, int i, vector<int>& v){
if(l + 1 == r) return cache[i] = {v[l], l};
int m = l + (r-l)/2;
return cache[i] = min(build(l, m, i*2+1, v), build(m, r, i*2+2, v));
}
pair<int, int> query(int l, int r, int i, int ql, int qr){
if(qr <= l || r <= ql) return {numeric_limits<int>::max(), numeric_limits<int>::max()};
if(ql <= l && r <= qr) return cache[i];
int m = l + (r-l)/2;
return min(query(l, m, i*2+1, ql, qr), query(m, r, i*2+2, ql, qr));
}
};
signed main(){
int n; cin >> n;
int half = fastpow(2, module-2);
vector<int> height (n);
vector<int> width (n);
for(int reader = 0; reader < n; reader++) cin >> height[reader];
for(int reader = 0; reader < n; reader++) cin >> width[reader];
segtree mint (n); mint.build(0, n, 0, height);
vector<int> pref = {0}; for(int summer = 0; summer < n; summer++) pref.push_back(pref.back()+width[summer]);
#define mul(x, y) x *= y; x %= module
auto from = [&](auto&& self, int l, int r, int to) -> pair<int, int>{
if(l >= r) return {0,0};
if(l+1 == r){
int w = width[l], h = height[l] - to;
int in = 1;
mul(in, w);
mul(in, w+1);
mul(in, half);
mul(in, h);
mul(in, h+1);
mul(in, half);
int bot = 1;
mul(bot, w);
mul(bot, w+1);
mul(bot, half);
mul(bot, h);
return {in, bot};
}
vector<int> splits; int lowest = numeric_limits<int>::max(); int li = l;
while(true){
pair<int, int> got = mint.query(0, n, 0, li, r);
if(got.first <= lowest){
lowest = got.first;
splits.push_back(got.second);
li = got.second+1;
}
else{
break;
}
}
splits.push_back(r);
int h = lowest-to;
int w = pref[r] - pref[l];
int sum_in = 0, sum_bot = 0;
int prev = l;
for(int seg : splits){
pair<int, int> got = self(self, prev, seg, lowest);
sum_in += got.first; sum_in %= module;
sum_bot += got.second; sum_bot %= module;
sum_in += got.second * h;
prev = seg+1;
}
int in;
mul(in, w);
mul(in, w+1);
mul(in, half);
mul(in, h);
mul(in, h+1);
mul(in, half);
int bot;
mul(bot, w);
mul(bot, w+1);
mul(bot, half);
mul(bot, h);
return {sum_in + in, sum_bot + bot};
};
pair<int, int> got = from(from, 0, n, 0);
cout << got.first;
return 0;
}
Compilation message
fancyfence.cpp: In lambda function:
fancyfence.cpp:50:21: warning: 'in' may be used uninitialized in this function [-Wmaybe-uninitialized]
50 | #define mul(x, y) x *= y; x %= module
| ^~
fancyfence.cpp:94:13: note: 'in' was declared here
94 | int in;
| ^~
fancyfence.cpp:50:21: warning: 'bot' may be used uninitialized in this function [-Wmaybe-uninitialized]
50 | #define mul(x, y) x *= y; x %= module
| ^~
fancyfence.cpp:101:13: note: 'bot' was declared here
101 | int bot;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
