Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define int long long
- #define boost ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
- using namespace std;
- const int mod = 1e9 + 7;
- vector<int> h, w, pref;
- int ans = 0;
- int bpow(int a, int n) {
- int res = 1;
- while(n > 0) {
- if(n & 1) {
- res *= a;
- res %= mod;
- }
- a *= a;
- a %= mod;
- n /= 2;
- }
- return res;
- }
- int C(int n, int k = 2) {
- int res = 1;
- for(int i = 1; i <= k; i++) {
- res = ((res * ((n - k + i) % mod)) % mod) * bpow(i, mod - 2);
- }
- return res;
- }
- //sub4
- void solvesame() {
- int y = h[0];
- int x = 0;
- for(auto it: w) {
- x = (x + it) % mod;
- }
- cout << ((C(x + 1, 2) % mod) * (C(y + 1, 2) % mod)) % mod << endl;
- }
- //sub3
- void solvesub3() {
- int n = h.size();
- int x = 0;
- for(auto it: w) {
- x = (x + it) % mod;
- }
- int ans = ((C(x + 1, 2) % mod));
- int prev = 0;
- for(int i = 0; i < n; i++) {
- if(h[i] == 1) {
- ans = (ans + ((C(prev + 1, 2) % mod) * (C(3, 2) % mod)) % mod) % mod;
- ans = (ans - (C(prev + 1, 2) % mod) + mod) % mod;
- prev = 0;
- } else {
- prev += w[i];
- }
- }
- ans = (ans + ((C(prev + 1, 2) % mod) * (C(3, 2) % mod)) % mod) % mod;
- ans = (ans - (C(prev + 1, 2) % mod) + mod) % mod;
- cout << ans << endl;
- }
- void solvesub5() {
- int n = h.size();
- int x = 0;
- for(auto it: w) {
- x = (x + it) % mod;
- }
- int ans = ((C(x + 1, 2) % mod) * (C(h[0] + 1, 2) % mod)) % mod;
- x = (x - w[0] + mod) % mod;
- for(int i = 1; i < n; i++) {
- ans = (ans + ((C(x + 1, 2) % mod) * (C(h[i] + 1, 2) % mod)) % mod) % mod;
- ans = (ans - ((C(x + 1, 2) % mod) * (C(h[i - 1] + 1, 2) % mod)) % mod + mod) % mod;
- x = (x - w[i] + mod) % mod;
- }
- cout << ans << endl;
- }
- void solvesub2() {
- int mxh = *max_element(h.begin(), h.end());
- int ans = 0;
- int n = h.size();
- for(int hi = 1; hi <= mxh; hi++) {
- int prev = 0;
- for(int i = 0; i < n; i++) {
- if(h[i] >= hi) {
- prev = (prev + w[i]) % mod;
- } else {
- ans = (ans + ((C(prev + 1, 2) % mod) * (C(hi + 1, 2) % mod)) % mod) % mod;
- ans = (ans - ((C(prev + 1, 2) % mod) * (C(hi, 2) % mod)) % mod + mod) % mod;
- prev = 0;
- }
- }
- ans = (ans + ((C(prev + 1, 2) % mod) * (C(hi + 1, 2) % mod)) % mod) % mod;
- ans = (ans - ((C(prev + 1, 2) % mod) * (C(hi, 2) % mod)) % mod + mod) % mod;
- }
- cout << ans << endl;
- }
- void solvesub6() {
- int ans = 0;
- int n = h.size();
- vector<int> his = h;
- sort(his.begin(), his.end());
- for(int hi = 0; hi < n; hi++) {
- int prev = 0;
- for(int i = 0; i < n; i++) {
- if(h[i] >= his[hi]) {
- prev = (prev + w[i]) % mod;
- } else {
- ans = (ans + ((C(prev + 1, 2) % mod) * (C(his[hi] + 1, 2) % mod)) % mod) % mod;
- if(hi > 0) ans = (ans - ((C(prev + 1, 2) % mod) * (C(his[hi - 1] + 1, 2) % mod)) % mod + mod) % mod;
- prev = 0;
- }
- }
- ans = (ans + ((C(prev + 1, 2) % mod) * (C(his[hi] + 1, 2) % mod)) % mod) % mod;
- if(hi > 0) ans = (ans - ((C(prev + 1, 2) % mod) * (C(his[hi - 1] + 1, 2) % mod)) % mod + mod) % mod;
- }
- cout << ans << endl;
- }
- main() {
- boost;
- int n;
- cin >> n;
- h.resize(n), w.resize(n), pref.resize(n + 1);
- for(int i = 0; i < n; i++) {
- cin >> h[i];
- }
- for(int i = 0; i < n; i++) {
- cin >> w[i];
- pref[i + 1] = pref[i] + w[i];
- }
- //subtasks
- bool sub4 = 1;
- bool sub3 = (h[0] <= 2);
- bool sub5 = 1;
- bool sub2 = (n <= 50 && h[0] <= 50);
- bool sub6 = (n <= 1000);
- //end subtasks
- //check subtask
- for(int i = 1; i < n; i++) {
- sub4 &= (h[i] == h[i - 1]);
- sub3 &= (h[i] <= 2);
- sub5 &= (h[i - 1] <= h[i]);
- sub2 &= (h[i] <= 50);
- }
- if(sub2) {
- solvesub2();
- return 0;
- }
- if(sub3) {
- solvesub3();
- return 0;
- }
- if(sub4) {
- solvesame();
- return 0;
- }
- if(sub5) {
- solvesub5();
- return 0;
- }
- if(sub6) {
- solvesub6();
- return 0;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement