#include <iostream>
#include <vector>
using namespace std;
#define int int64_t
vector<int> tree;
vector<bool> lazy;
void push(int v) {
if (v*2+1 >= tree.size()) return;
lazy[v*2] = lazy[v];
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];
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 * ((pos+1.0)/2.0 * 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);
}
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;
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);
}
int valBefore = 0;
int resOverlap = 0;
int resOneSeg = 0;
for (int i = 0; i<n; i++) {
int h = 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);
// 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;
// cout << resOverlap << "\n";
resOneSeg += ((w+1.0)/2.0 * w) * ((h+1.0)/2.0 * h);
}
cout << resOverlap + resOneSeg << "\n";
// cout << resOverlap << " + " << resOneSeg << "\n";
return 0;
}
Compilation message
fancyfence.cpp: In function 'void push(int64_t)':
fancyfence.cpp:12: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]
12 | if (v*2+1 >= tree.size()) return;
| ~~~~~~^~~~~~~~~~~~~~
fancyfence.cpp: In function 'void push2(int64_t)':
fancyfence.cpp:75: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]
75 | if (v*2+1 >= tree2.size()) return;
| ~~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
16204 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
16192 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
16108 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 |
11 ms |
16148 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
16204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
16184 KB |
Output is correct |
| 2 |
Incorrect |
13 ms |
16204 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
16184 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
16280 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
16204 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
16192 KB |
Output isn't correct |
