#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
#define int long long
typedef int64_t ll;
typedef long double ld;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define pb emplace_back
#define mp make_pair
#define mt make_tuple
#define pii pair<int,int>
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
#define RF(n) RFi(i,n)
#define RFi(i,n) RFl(i,0,n)
#define RFl(i,l,n) for(int i=n-1;i>=l;i--)
#define all(v) begin(v),end(v)
#define siz(v) (ll(v.size()))
#define get_pos(v,x) (lower_bound(all(v),x)-begin(v))
#define sort_uni(v) sort(begin(v),end(v)),v.erase(unique(begin(v),end(v)),end(v))
#define mem(v,x) memset(v,x,sizeof v)
#define ff first
#define ss second
#define mid ((l+r)>>1)
#define RAN(a,b) uniform_int_distribution<int> (a, b)(rng)
template <typename T> using max_heap = __gnu_pbds::priority_queue<T,less<T> >;
template <typename T> using min_heap = __gnu_pbds::priority_queue<T,greater<T> >;
template <typename T> using rbt = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const int mod = 1e9+7;
signed main(){
int n;
cin >> n;
pii section[n+1];
F(n) cin >> section[i+1].ff;
F(n) cin >> section[i+1].ss;
int prefix_w[n+1];
prefix_w[0] = 0;
F(n){
prefix_w[i+1] = prefix_w[i] + section[i+1].ss;
}
pii sorting[n];
F(n){
sorting[i] = {section[i+1].ff, i+1};
}
sort(sorting, sorting + n);
set<int> processed;
processed.insert(0);
processed.insert(n+1);
int ans = 0;
F(n){
// process i;
pii curr = sorting[i];
auto it = processed.lower_bound(curr.ss);
int ub = *it;
it--;
int lb = *it;
ub--;
lb++;
int w1,w2,w3;
w1 = prefix_w[curr.ss-1] - prefix_w[lb-1];
w2 = section[curr.ss].ss;
w3 = prefix_w[ub] - prefix_w[curr.ss];
w1 %= mod;
w3 %= mod;
ans += ((w1*w2%mod) * (((curr.ff+1) * curr.ff / 2) % mod)) % mod;
ans %= mod;
ans += ((w3*w2%mod) * (((curr.ff+1) * curr.ff / 2) % mod)) % mod;
ans %= mod;
ans += ((w3*w1%mod) * (((curr.ff+1) * curr.ff / 2) % mod)) % mod;
ans %= mod;
ans += ((((w2+1) * w2 / 2) % mod) * (((curr.ff+1) * curr.ff / 2) % mod)) % mod;
ans %= mod;
processed.insert(curr.ss);
}
printf("%lld", ans);
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
2 ms |
332 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
2 ms |
332 KB |
Output is correct |
3 |
Correct |
50 ms |
5084 KB |
Output is correct |
4 |
Correct |
86 ms |
10004 KB |
Output is correct |
5 |
Correct |
88 ms |
10012 KB |
Output is correct |
6 |
Correct |
100 ms |
10020 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
11 ms |
1276 KB |
Output is correct |
3 |
Correct |
57 ms |
5516 KB |
Output is correct |
4 |
Correct |
113 ms |
10788 KB |
Output is correct |
5 |
Correct |
108 ms |
10904 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
15 ms |
1256 KB |
Output is correct |
4 |
Correct |
63 ms |
5516 KB |
Output is correct |
5 |
Correct |
118 ms |
10792 KB |
Output is correct |
6 |
Correct |
108 ms |
10832 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
10 ms |
1324 KB |
Output is correct |
9 |
Correct |
53 ms |
5572 KB |
Output is correct |
10 |
Correct |
107 ms |
10656 KB |
Output is correct |
11 |
Correct |
111 ms |
10776 KB |
Output is correct |
12 |
Correct |
0 ms |
204 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
2 ms |
332 KB |
Output is correct |
15 |
Correct |
2 ms |
332 KB |
Output is correct |
16 |
Correct |
0 ms |
204 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
2 ms |
332 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
0 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
40 ms |
5148 KB |
Output is correct |
12 |
Correct |
92 ms |
9948 KB |
Output is correct |
13 |
Correct |
90 ms |
10020 KB |
Output is correct |
14 |
Correct |
78 ms |
10012 KB |
Output is correct |
15 |
Correct |
2 ms |
332 KB |
Output is correct |
16 |
Correct |
10 ms |
1228 KB |
Output is correct |
17 |
Correct |
55 ms |
5524 KB |
Output is correct |
18 |
Correct |
108 ms |
10820 KB |
Output is correct |
19 |
Correct |
116 ms |
10844 KB |
Output is correct |
20 |
Correct |
2 ms |
308 KB |
Output is correct |
21 |
Correct |
10 ms |
1276 KB |
Output is correct |
22 |
Correct |
55 ms |
5572 KB |
Output is correct |
23 |
Correct |
104 ms |
10652 KB |
Output is correct |
24 |
Correct |
106 ms |
10696 KB |
Output is correct |
25 |
Correct |
1 ms |
204 KB |
Output is correct |
26 |
Correct |
1 ms |
332 KB |
Output is correct |
27 |
Correct |
1 ms |
332 KB |
Output is correct |
28 |
Correct |
1 ms |
332 KB |
Output is correct |
29 |
Correct |
2 ms |
332 KB |
Output is correct |
30 |
Correct |
11 ms |
1356 KB |
Output is correct |
31 |
Correct |
12 ms |
1280 KB |
Output is correct |
32 |
Correct |
61 ms |
5400 KB |
Output is correct |
33 |
Correct |
61 ms |
5460 KB |
Output is correct |
34 |
Correct |
128 ms |
10540 KB |
Output is correct |
35 |
Correct |
110 ms |
10520 KB |
Output is correct |
36 |
Correct |
138 ms |
10796 KB |
Output is correct |
37 |
Correct |
121 ms |
10820 KB |
Output is correct |
38 |
Correct |
0 ms |
204 KB |
Output is correct |
39 |
Correct |
122 ms |
10980 KB |
Output is correct |
40 |
Correct |
116 ms |
10780 KB |
Output is correct |
41 |
Correct |
106 ms |
10780 KB |
Output is correct |
42 |
Correct |
104 ms |
10748 KB |
Output is correct |