#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
#define int int64_t
vector<int> tree;
vector<bool> lazy;
map<int, int> dict;
vector<int> dictReverse;
int mod = 1000000007;
void push(int v) {
if (v*2+1 >= tree.size()) return;
lazy[v*2] = lazy[v*2]||lazy[v];
lazy[v*2+1] = lazy[v*2+1]||lazy[v];
if (lazy[v]){
tree[v*2] = 0;
tree[v*2+1] = 0;
}
lazy[v] = 0;
}
void updateRange(int v, int rl, int rr, int ql, int qr) {
if (ql > qr) return;
push(v);
if (rl == ql && rr == qr) {
// cout << rl << " " << rr << "\n";
tree[v] = 0;
lazy[v] = 1;
return;
}
int rm = (rl + rr) / 2;
updateRange(v*2, rl, rm, ql, min(rm, qr));
updateRange(v*2+1, rm+1, rr, max(ql, rm+1), qr);
tree[v] = tree[v*2] + tree[v*2+1];
}
void updatePos(int v, int rl, int rr, int pos, int val) {
push(v);
if (rl == rr) {
tree[v] += val;
// cout << rl << " blub\n";
return;
}
int rm = (rl + rr) / 2;
if (pos <= rm) updatePos(v*2, rl, rm, pos, val);
else updatePos(v*2+1, rm+1, rr, pos, val);
tree[v] = tree[v*2] + tree[v*2+1];
}
int querry(int v, int rl, int rr, int ql, int qr) {
if (ql > qr) return 0;
push(v);
if (rl == ql && rr == qr) {
return tree[v];
}
int rm = (rl + rr) / 2;
return querry(v*2, rl, rm, ql, min(qr, rm)) + querry(v*2+1, rm+1, rr, max(ql, rm+1), qr);
}
vector<int> tree2;
vector<bool> lazy2;
void push2(int v) {
if (v*2+1 >= tree2.size()) return;
lazy2[v*2] = lazy2[v*2]||lazy2[v];
lazy2[v*2+1] = lazy2[v*2+1]||lazy2[v];
if (lazy2[v]){
tree2[v*2] = 0;
tree2[v*2+1] = 0;
}
lazy2[v] = 0;
}
void updateRange2(int v, int rl, int rr, int ql, int qr) {
if (ql > qr) return;
push2(v);
if (rl == ql && rr == qr) {
tree2[v] = 0;
lazy2[v] = 1;
return;
}
int rm = (rl + rr) / 2;
updateRange2(v*2, rl, rm, ql, min(rm, qr));
updateRange2(v*2+1, rm+1, rr, max(ql, rm+1), qr);
tree2[v] = tree2[v*2] + tree2[v*2+1];
}
void updatePos2(int v, int rl, int rr, int pos, int val) {
push2(v);
if (rl == rr) {
tree2[v] += val * ((dictReverse[pos]+1.0)/2.0 * dictReverse[pos]);
return;
}
int rm = (rl + rr) / 2;
if (pos <= rm) updatePos2(v*2, rl, rm, pos, val);
else updatePos2(v*2+1, rm+1, rr, pos, val);
tree2[v] = tree2[v*2] + tree2[v*2+1];
}
int querry2(int v, int rl, int rr, int ql, int qr) {
if (ql > qr) return 0;
push2(v);
if (rl == ql && rr == qr) {
return tree2[v];
}
int rm = (rl + rr) / 2;
return querry2(v*2, rl, rm, ql, min(qr, rm)) + querry2(v*2+1, rm+1, rr, max(ql, rm+1), qr);
}
pair<vector<int>, vector<int>> simplify(vector<int> height, vector<int> width) {
vector<int> newheight; vector<int> newwidth;
for (int i = 0; i<height.size(); i++) {
for (int j = 0; j<width[i]; j++) {
newheight.push_back(height[i]);
newwidth.push_back(1);
}
}
return {newheight, newwidth};
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int n; cin >> n;
tree.assign(1000000, 0);
lazy.assign(1000000, 0);
tree2.assign(1000000, 0);
lazy2.assign(1000000, 0);
vector<int> height;
vector<int> width;
pair<vector<int>, vector<int>> blub = simplify(height, width);
height = blub.first;
width = blub.second;
for (int i = 0; i<n; i++) {
int tmp; cin >> tmp; height.push_back(tmp);
}
for (int i = 0; i<n; i++) {
int tmp; cin >> tmp; width.push_back(tmp);
}
vector<int> sortedHeight = height;
sort(sortedHeight.begin(), sortedHeight.end());
int counter = 0;
for (int i: sortedHeight) {
dict[i]=counter;
dictReverse.push_back(i);
counter++;
}
int valBefore = 0;
int resOverlap = 0;
int resOneSeg = 0;
for (int i = 0; i<n; i++) {
int h = dict[height[i]];
int w = width[i];
// cout << h << " " << w << "\n";
// for (int i=0; i<10; i++) {
// cout << querry(1, 0, 100000, i, i) << " ";
// }
// cout << "\n";
int tooBigSum = querry(1, 0, 100000, h, 100000);
updateRange(1, 0, 100000, h, 100000);
updateRange2(1, 0, 100000, h, 100000);
updatePos(1, 0, 100000, h, tooBigSum);
updatePos2(1, 0, 100000, h, tooBigSum);
valBefore = querry2(1, 0, 100000, 0, 100000)%mod;
// for (int i=0; i<10; i++) {
// cout << querry(1, 0, 100000, i, i) << " ";
// }
// cout << "\n";
updatePos(1, 0, 100000, h, w);
updatePos2(1, 0, 100000, h, w);
// cout << querry(1, 0, 100000, h, h) << "\n";
resOverlap += (valBefore * w)%mod;
// cout << resOverlap << "\n";
resOneSeg += int((w+1.0)/2.0 * w)%mod * int((dictReverse[h]+1.0)/2.0 * dictReverse[h])%mod;
}
cout << (resOverlap + resOneSeg)%mod << "\n";
// cout << resOverlap << " + " << resOneSeg << "\n";
return 0;
}
//signed main() {
// int n, q; cin >> n >> q;
// tree.assign(n*4, 0);
// lazy.assign(n*4, 0);
// tree2.assign(n*4, 0);
// lazy2.assign(n*4, 0);
//
// for (int i = 0; i<q; i++) {
// char c; cin >> c;
// if (c == 'q') {
// int left, right; cin >> left >> right;
// cout << querry(1, 0, n-1, left, right) << "\n";
// }
// if (c == 'r') {
// int left, right; cin >> left >> right;
// updateRange(1, 0, n-1, left, right);
// }
// if (c == 'p') {
// int pos, val; cin >> pos >> val;
// updatePos(1, 0, n-1, pos, val);
// }
// }
//}
Compilation message
fancyfence.cpp: In function 'void push(int64_t)':
fancyfence.cpp:16:15: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
16 | if (v*2+1 >= tree.size()) return;
| ~~~~~~^~~~~~~~~~~~~~
fancyfence.cpp: In function 'void push2(int64_t)':
fancyfence.cpp:78:15: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | if (v*2+1 >= tree2.size()) return;
| ~~~~~~^~~~~~~~~~~~~~~
fancyfence.cpp: In function 'std::pair<std::vector<long int>, std::vector<long int> > simplify(std::vector<long int>, std::vector<long int>)':
fancyfence.cpp:134:22: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
134 | for (int i = 0; i<height.size(); i++) {
| ~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
16204 KB |
Output is correct |
| 2 |
Incorrect |
11 ms |
16204 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
16204 KB |
Output is correct |
| 2 |
Correct |
8 ms |
16212 KB |
Output is correct |
| 3 |
Correct |
8 ms |
16224 KB |
Output is correct |
| 4 |
Correct |
9 ms |
16204 KB |
Output is correct |
| 5 |
Correct |
8 ms |
16204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
16204 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
16204 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
16204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
16204 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
16204 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
16204 KB |
Output is correct |
| 2 |
Incorrect |
12 ms |
16296 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
16204 KB |
Output is correct |
| 2 |
Incorrect |
11 ms |
16204 KB |
Output isn't correct |
