#include <bits/stdc++.h>
using namespace std;
struct Star {
int x, y;
int c;
int slq; // segment tree left query range
int srq; // " right query range
int rl, rr; // reporting l, reporting r
Star(int x, int y, int c)
: x(x), y(y), c(c), slq(-1), srq(-1), rl(-1), rr(-1) {};
};
struct Seg {
int n;
vector<int64_t> seg;
Seg(int _n) : n(_n), seg(2 * _n, 0) {};
int64_t sum(int l, int r) {
l += n, r += n;
int64_t ret = 0;
while (l < r) {
if (l & 1) {
ret += seg[l];
l += 1;
}
if (r & 1) {
r -= 1;
ret += seg[r];
}
l /= 2, r /= 2;
}
return ret;
}
int64_t at(int i) {
return seg[i + n];
}
void set(int i, int64_t val) {
i += n;
seg[i] = val;
while (i > 1) {
i /= 2;
seg[i] = seg[2 * i] + seg[2 * i + 1];
}
}
};
int n, m;
vector<int> a;
vector<vector<int>> to_zero_l, to_zero_r;
vector<Star> stars;
vector<vector<int>> stars_by_x;
vector<int64_t> stars_max_c, buildings_profit_l, buildings_profit_r;
vector<int> buildings_rl, buildings_rr;
void solve() {
cin >> n;
a.resize(n), stars_by_x.assign(n + 1, {});
for (auto& a : a) cin >> a;
a.push_back(1000000);
n += 1;
to_zero_l.assign(n, {});
to_zero_r.assign(n, {});
buildings_profit_l.assign(n, 0), buildings_profit_r.assign(n, 0);
buildings_rl.assign(n, 0), buildings_rr.assign(n, 0);
cin >> m;
for (int i = 0; i < m; ++i) {
int x, y, c;
cin >> x >> y >> c;
x -= 1;
stars.push_back(Star(x, y, c));
}
stars.push_back(Star(n - 1, 1000001, 0));
m += 1;
stars_max_c.assign(m, 0);
sort(stars.begin(), stars.end(),
[&](const Star& lhs, const Star& rhs) { return lhs.x < rhs.x; });
for (int i = 0; i < stars.size(); ++i) {
stars_by_x[stars[i].x].push_back(i);
}
// add left and right query
for (auto is_left : {true, false}) {
auto report = [&](Star& x) -> int& { return is_left ? x.rl : x.rr; };
auto seg_query = [&](Star& x) -> int& {
return is_left ? x.slq : x.srq;
};
auto to_zero = [&](int i) -> vector<int>& {
return is_left ? to_zero_l[i] : to_zero_r[i];
};
auto building_report = [&](int i) -> int& {
return is_left ? buildings_rl[i] : buildings_rr[i];
};
vector<pair<int, int>> cur_buildings;
set<pair<int, int>> cur_stars;
int i = is_left ? 0 : a.size() - 1;
while (is_left ? i < a.size() : i >= 0) {
pair<int, int> cur = {a[i], i};
while (!cur_buildings.empty() && cur_buildings.back() < cur) {
to_zero(i).push_back(cur_buildings.back().second);
building_report(cur_buildings.back().second) = i;
cur_buildings.pop_back();
}
cur_buildings.push_back(cur);
while (!cur_stars.empty()) {
int fst_idx = cur_stars.begin()->second;
if (stars[fst_idx].y > a[i]) {
break;
}
report(stars[fst_idx]) = i;
cur_stars.erase(cur_stars.begin());
}
for (auto s : stars_by_x[i]) {
auto it =
lower_bound(cur_buildings.rbegin(), cur_buildings.rend(),
make_pair(stars[s].y, INT_MIN));
int query_idx = it == cur_buildings.rend() ? -1 : it->second;
seg_query(stars[s]) = query_idx;
cur_stars.insert({stars[s].y, s});
}
i = is_left ? i + 1 : i - 1;
}
}
// y, idx, is star
vector<tuple<int, int, bool>> stars_buildings;
for (int i = 0; i < stars.size(); ++i) {
int y = stars[i].y;
stars_buildings.push_back({y, i, true});
}
for (int i = 0; i < a.size(); ++i) {
stars_buildings.push_back({a[i], i, false});
}
sort(stars_buildings.begin(), stars_buildings.end(),
[&](const tuple<int, int, bool>& a, const tuple<int, int, bool>& b) {
if (get<0>(a) == get<0>(b)) {
return get<2>(a) > get<2>(b);
}
return get<0>(a) < get<0>(b);
});
Seg seg_l(n), seg_r(n);
for (auto [_, idx, is_star] : stars_buildings) {
if (is_star) {
if (idx == 3) {
int x = 3;
}
Star cur = stars[idx];
int64_t left_sum = seg_l.sum(cur.slq + 1, cur.x + 1);
int64_t right_sum = seg_r.sum(cur.x, cur.srq == -1 ? n : cur.srq);
int64_t cur_profit = left_sum + cur.c + right_sum;
stars_max_c[idx] = cur_profit;
buildings_profit_l[cur.rl] = max(buildings_profit_l[cur.rl], cur_profit);
buildings_profit_r[cur.rr] = max(buildings_profit_r[cur.rr], cur_profit);
} else {
int64_t cur_profit_l = 0;
for (auto to_zero : to_zero_l[idx]) {
cur_profit_l += buildings_profit_l[to_zero];
// seg_r.set(to_zero, 0);
}
seg_l.set(idx, buildings_profit_l[idx] - cur_profit_l);
int64_t cur_profit_r = 0;
for (auto to_zero : to_zero_r[idx]) {
cur_profit_r += buildings_profit_r[to_zero];
// seg_r.set(to_zero, 0);
}
seg_r.set(idx, buildings_profit_r[idx] - cur_profit_r);
buildings_profit_l[buildings_rl[idx]] += buildings_profit_l[idx];
buildings_profit_r[buildings_rr[idx]] += buildings_profit_r[idx];
}
}
int64_t sum_c = 0;
for (auto star : stars) sum_c += star.c;
cout << sum_c - stars_max_c[m - 1] << "\n";
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int t = 1;
solve();
}
Compilation message
constellation3.cpp: In function 'void solve()':
constellation3.cpp:88:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Star>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
88 | for (int i = 0; i < stars.size(); ++i) {
| ~~^~~~~~~~~~~~~~
constellation3.cpp:107:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
107 | while (is_left ? i < a.size() : i >= 0) {
| ~~^~~~~~~~~~
constellation3.cpp:141:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Star>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
141 | for (int i = 0; i < stars.size(); ++i) {
| ~~^~~~~~~~~~~~~~
constellation3.cpp:145:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
145 | for (int i = 0; i < a.size(); ++i) {
| ~~^~~~~~~~~~
constellation3.cpp:162:21: warning: unused variable 'x' [-Wunused-variable]
162 | int x = 3;
| ^
constellation3.cpp: In function 'int main()':
constellation3.cpp:199:9: warning: unused variable 't' [-Wunused-variable]
199 | int t = 1;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
