#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
ll N, H[500007], W[500007];
const ll mod = 1e9 + 7;
void initialize() {
ios_base :: sync_with_stdio(0);
cin.tie(0); cout.tie(0);
if (fopen("FILE.INP", "r")) {
freopen("FILE.INP", "r", stdin);
freopen("FILE.OUT", "w", stdout);
}
cin >> N;
for(int i = 1; i <= N; ++i) cin >> H[i];
for(int i = 1; i <= N; ++i) cin >> W[i];
}
namespace subtask2 {
ll A[1007][1007];
void solve() {
ll lastw = 0;
for(int i = 1; i <= N; ++i) {
for(int h = 1; h <= H[i]; ++h) {
for(int w = lastw + 1; w <= lastw + W[i]; ++w) {
A[h][w] = 1;
}
}
lastw += W[i];
}
/*for(int i = 1; i <= 50; ++i) {
for(int j = 1; j <= 50; ++j) {
cerr << A[i][j];
}
cerr << endl;
}*/
for(int i = 1; i <= 50; ++i) {
for(int j = 1; j <= 50; ++j) {
A[i][j] = A[i][j - 1] + A[i - 1][j] + A[i][j] - A[i - 1][j - 1];
}
}
ll ans = 0;
for(int i = 1; i <= 50; ++i) {
for(int j = 1; j <= 50; ++j) {
for(int k = i; k <= 50; ++k) {
for(int l = j; l <= 50; ++l) {
ans += (A[k][l] - A[i - 1][l] - A[k][j - 1] + A[i - 1][j - 1])
== ((k - i + 1) * (l - j + 1));
}
}
}
}
cout << ans;
}
void process() {
memset(A, 0, sizeof(A));
solve();
}
}
namespace subtask3 {
ll fsum(ll n) {
ll x1 = n;
ll x2 = n + 1;
if (x1 % 2 == 0) x1 /= 2;
else x2 /= 2;
x1 %= mod;
x2 %= mod;
return (x1 * x2) % mod;
}
void solve() {
vector<ll> split;
split.push_back(0);
for(int i = 1; i <= N; ++i) {
if (H[i] == 1 && split.back() > 0) split.push_back(0);
if (H[i] == 2) split[split.size() - 1] += W[i];
}
ll sum1 = accumulate(W + 1, W + 1 + N, 0LL);
sum1 = fsum(sum1);
ll sum2 = 0;
for(ll c : split) {
sum2 = (sum2 + fsum(c));
sum2 %= mod;
}
sum2 = (sum2 * 2) % mod;
cout << (sum1 + sum2) % mod;
}
void process() {
solve();
}
}
namespace subtask4 {
ll fsum(ll n) {
ll x1 = n;
ll x2 = n + 1;
if (x1 % 2 == 0) x1 /= 2;
else x2 /= 2;
x1 %= mod;
x2 %= mod;
return (x1 * x2) % mod;
}
void solve() {
ll sum1 = H[1];
ll sum2 = accumulate(W + 1, W + 1 + N, 0LL);
//cerr << sum1 << " " << sum2 << endl;
cout << (fsum(sum1) * fsum(sum2)) % mod;
}
void process() {
solve();
}
}
namespace subtask5 {
ll fsum(ll n) {
ll x1 = n;
ll x2 = n + 1;
if (x1 % 2 == 0) x1 /= 2;
else x2 /= 2;
x1 %= mod;
x2 %= mod;
return (x1 * x2) % mod;
}
void solve() {
ll sum = accumulate(W + 1, W + 1 + N, 0LL);
ll ans = 0;
for(int i = 1; i <= N; ++i) {
ll total = (fsum(sum) * fsum(H[i])) % mod;
total -= (fsum(sum) * fsum(H[i - 1])) % mod;
total = (total + mod) % mod;
ans = (ans + total) % mod;
sum -= W[i];
}
cout << ans;
}
void process() {
solve();
}
}
namespace subtask6 {
ll fsum(ll n) {
ll x1 = n;
ll x2 = n + 1;
if (x1 % 2 == 0) x1 /= 2;
else x2 /= 2;
x1 %= mod;
x2 %= mod;
return (x1 * x2) % mod;
}
ll rmin[1007][1007];
void rmin_calculate() {
for(int i = 1; i <= N; ++i) {
rmin[i][i] = H[i];
for(int j = i + 1; j <= N; ++j) {
rmin[i][j] = min(rmin[i][j - 1], H[j]);
}
}
/*for(int i = 1; i <= N; ++i) {
for(int j = i; j <= N; ++j) {
cerr << i << " " << j << " " << rmin[i][j] << endl;
}
}*/
}
void solve() {
ll ans = 0;
for(int i = 1; i <= N; ++i) {
ans += (fsum(H[i]) * fsum(W[i])) % mod;
ans %= mod;
}
for(int i = 1; i <= N; ++i) {
for(int j = i + 1; j <= N; ++j) {
ll total = fsum(rmin[i][j]);
total = (total * W[i]) % mod;
total = (total * W[j]) % mod;
ans += total;
ans %= mod;
/*cerr << i << " " << j << endl;
cerr << rmin[i][j] << " " << W[i] << " " << W[j] << " " << total << endl;
cerr << endl;*/
}
}
cout << ans;
}
void process() {
rmin_calculate();
solve();
}
}
namespace subtask7 {
ll fsum(ll n) {
ll x1 = n;
ll x2 = n + 1;
if (x1 % 2 == 0) x1 /= 2;
else x2 /= 2;
x1 %= mod;
x2 %= mod;
return (x1 * x2) % mod;
}
void Cong(ll& a, ll b) {
a = ((a % mod) + (b % mod)) % mod;
}
ll Tong(ll a, ll b) {
return ((a % mod) + (b % mod)) % mod;
}
void Tru(ll& a, ll b) {
a = ((a % mod) - (b % mod) + mod) % mod;
}
ll Hieu(ll a, ll b) {
return ((a % mod) - (b % mod) + mod) % mod;
}
void Nhan(ll& a, ll b) {
a = ((a % mod) * (b % mod)) % mod;
}
ll Tich(ll a, ll b) {
return ((a % mod) * (b % mod)) % mod;
}
pair<pair<ll, ll>, ll> A[100007];
set<pair<ll, ll>> se;
ll PreSumW[100007];
ll ans = 0;
ll fsum_segment = 0;
void pre_process() {
for(int i = 1; i <= N; ++i) A[i] = {{H[i], W[i]}, i};
se.insert({1, N});
for(int i = 1; i <= N; ++i) PreSumW[i] = PreSumW[i - 1] + W[i];
sort(A + 1, A + 1 + N);
fsum_segment = fsum(accumulate(W + 1, W + 1 + N, 0LL));
ans = Tich(fsum_segment, A[1].first.first);
}
void solve() {
for(int i = 1; i <= N; ++i) {
if (A[i].first.first > A[i - 1].first.first) {
ll tmp = Tich(fsum_segment, A[i].first.first);
Tru(tmp, Tich(fsum_segment, A[i - 1].first.first));
Cong(ans, tmp);
}
pair<ll, ll> s = *prev(se.lower_bound({A[i].second, 9999999999}));
assert(s.first <= A[i].second && A[i].second <= s.second);
Tru(fsum_segment, fsum(PreSumW[s.second] - PreSumW[s.first - 1]));
se.erase(s);
pair<ll, ll> sleft = {s.first, A[i].second - 1};
pair<ll, ll> sright = {A[i].second + 1, s.second};
if (sleft.first <= sleft.second) {
Cong(fsum_segment, fsum(PreSumW[sleft.second] - PreSumW[sleft.first - 1]));
se.insert(sleft);
}
if (sright.first <= sright.second) {
Cong(fsum_segment, fsum(PreSumW[sright.second] - PreSumW[sright.first]));
se.insert(sright);
}
}
cout << ans;
}
void process() {
pre_process();
solve();
}
}
int main() {
initialize();
ll maxh = *max_element(H + 1, H + 1 + N);
ll minh = *min_element(H + 1, H + 1 + N);
ll maxw = *max_element(W + 1, W + 1 + N);
ll minw = *min_element(W + 1, W + 1 + N);
subtask7 :: process();
}
Compilation message
fancyfence.cpp: In function 'int main()':
fancyfence.cpp:312:8: warning: unused variable 'maxh' [-Wunused-variable]
312 | ll maxh = *max_element(H + 1, H + 1 + N);
| ^~~~
fancyfence.cpp:313:8: warning: unused variable 'minh' [-Wunused-variable]
313 | ll minh = *min_element(H + 1, H + 1 + N);
| ^~~~
fancyfence.cpp:314:8: warning: unused variable 'maxw' [-Wunused-variable]
314 | ll maxw = *max_element(W + 1, W + 1 + N);
| ^~~~
fancyfence.cpp:315:8: warning: unused variable 'minw' [-Wunused-variable]
315 | ll minw = *min_element(W + 1, W + 1 + N);
| ^~~~
fancyfence.cpp: In function 'void initialize()':
fancyfence.cpp:13:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
13 | freopen("FILE.INP", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
fancyfence.cpp:14:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
14 | freopen("FILE.OUT", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
8536 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
8536 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
8536 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
8536 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
8540 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
8536 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
8540 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
8536 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
8536 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
