This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define int ll
using ll = long long;
using vi = vector<int>;
using ii = pair<int, int>;
const int MOD = 1e9 + 7;
const int inv2 = 5e8 + 4;
struct DSU {
int re = 0;
vi e, s;
DSU(int n, const vi &S0) : e(n, -1), s(S0) {}
int repr(int u) {
while(e[u] >= 0) u = e[u];
return u;
}
void join(int u, int v) {
u = repr(u);
v = repr(v);
if(u == v) return;
if(e[u] > e[v]) swap(u, v);
e[u] += e[v];
e[v] = u;
re = (re - 1ll * s[u] * (s[u] + 1) % MOD * int(5e8 + 4) % MOD) % MOD;
re = (re - 1ll * s[v] * (s[v] + 1) % MOD * int(5e8 + 4) % MOD) % MOD;
s[u] += s[v];
s[u] %= MOD;
re = (re + 1ll * s[u] * (s[u] + 1) % MOD * int(5e8 + 4) % MOD) % MOD;
re = (re + MOD) % MOD;
}
};
signed main() {
int n;
cin >> n;
vi W(n);
vector<ii> H(n);
for(int i = 0; i < n; ++i) {
cin >> H[i].first;
H[i].second = i;
}
for(int i = 0; i < n; ++i)
cin >> W[i];
DSU Sol(n, W);
vi on(n, 0);
sort(H.rbegin(), H.rend());
ll s = 0, ant = 0;
ll re = 0, hant = 0;
H.push_back({0, 0});
for(int i = 0; i < n; ++i) {
int dr = i;
do {
int p = H[dr].second;
s += 1ll * W[p] * (W[p] + 1) % MOD * inv2 % MOD;
s %= MOD;
on[p] = 1;
if(p && on[p - 1]) Sol.join(p, p - 1);
if(p + 1 < n && on[p + 1]) Sol.join(p, p + 1);
++dr;
} while(dr < n && H[dr].first == H[dr - 1].first);
int h = H[i].first;
int fact = h * (h + 1) % MOD * inv2 % MOD;
int uh = H[dr].first;
int f2 = uh * (uh + 1) % MOD * inv2 % MOD;
fact = fact - f2;
fact = (fact % MOD + MOD) % MOD;
ll cur = (s + Sol.re) % MOD;
re = (re + cur * fact % MOD) % MOD;
i = dr - 1;
}
cout << re << "\n";
return 0;
}
Compilation message (stderr)
fancyfence.cpp: In function 'int main()':
fancyfence.cpp:54:15: warning: unused variable 'ant' [-Wunused-variable]
54 | ll s = 0, ant = 0;
| ^~~
fancyfence.cpp:55:16: warning: unused variable 'hant' [-Wunused-variable]
55 | ll re = 0, hant = 0;
| ^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |