#include <iostream>
#include <vector>
#include <cassert>
#include <cmath>
#include <algorithm>
#include <set>
using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))
class SegmentTree{
private:
std::vector<std::pair<int,int>> aint;
public:
SegmentTree(int n) {
aint.resize(1 + 4 * n);
}
void computenode(int node, int from, int to) {
aint[node] = std::max(aint[node * 2] , aint[node * 2 + 1]);
}
void build(int node, int from, int to, std::vector<int> &aux) {
if(from < to) {
int mid = (from + to) / 2;
build(node * 2, from, mid, aux);
build(node * 2 + 1, mid + 1, to, aux);
computenode(node, from, to);
} else
aint[node] = {aux[from], from};
}
std::pair<int,int> query(int node, int from, int to, int x, int y) {
if(from == x && to == y)
return aint[node];
else {
int mid = (from + to) / 2;
if(x <= mid && y <= mid)
return query(node * 2, from, mid, x, y);
if(mid + 1 <= x && mid + 1 <= y)
return query(node * 2 + 1, mid + 1, to, x, y);
else
return std::max(query(node * 2, from, mid, x, mid),
query(node * 2 + 1, mid + 1, to, mid + 1, y));
}
}
};
int const nmax = 200000;
std::vector<std::vector<std::pair<int,int>>> event;
class SpecialSet{
public:
std::set<std::pair<int, ll>> myset;
ll offset = 0;
void update(ll val) {
offset += val;
}
void _insert(std::pair<int, ll> val) {
val.second -= offset;
std::set<std::pair<int,ll>>::iterator it = myset.upper_bound(val);
if(it == myset.begin())
myset.insert(val);
else {
it--;
if(val.second < it->second)
myset.insert(val);
}
it = myset.upper_bound(val);
while(it != myset.end() && val.second <= it->second)
myset.erase(it++);
}
ll extract(int wall) {
std::set<std::pair<int,ll>>::iterator it = myset.lower_bound({wall + 1, 0});
assert(it != myset.begin());
it--;
return it->second + offset;
}
int size() {
return myset.size();
}
void absorb(SpecialSet oth) {
std::set<std::pair<int, ll>>::iterator it = oth.myset.begin();
while(it != oth.myset.end()) {
_insert({it->first, it->second + oth.offset});
it++;
}
}
void print() {
std::cout << "Print\n";
for(std::set<std::pair<int, ll>>::iterator it = myset.begin(); it != myset.end(); it++)
std::cout << it->first << " " << it->second + offset << '\n';
std::cout << '\n';
}
};
int n;
std::vector<int> v;
void divide(int from, int to, SegmentTree &aint, SpecialSet &myset) {
if(from == to) {
ll result = 0;
for(int h = 0; h < event[from].size(); h++)
result += event[from][h].second;
myset._insert({0, result});
for(int h = 0; h < event[from].size(); h++)
myset._insert({event[from][h].first, result - event[from][h].second});
} else {
int mid = aint.query(1, 1, n, from, to).second;
int target = v[mid];
if(mid == to)
mid--;
SpecialSet myset1, myset2;
divide(from, mid, aint, myset1);
divide(mid + 1, to, aint, myset2);
ll upper1 = myset2.extract(target), upper2 = myset1.extract(target);
myset1.update(upper1);
myset2.update(upper2);
if(myset1.size() < myset2.size())
std::swap(myset1, myset2);
myset1.absorb(myset2);
std::swap(myset, myset1);
}
}
int main() {
std::ios::sync_with_stdio(0);
std::cin.tie(0);
std::cin >> n;
event.resize(1 + n);
v = std::vector<int>(1 + n);
for(int i = 1;i <= n; i++)
std::cin >> v[i];
int q;
std::cin >> q;
SegmentTree aint(n);
aint.build(1, 1, n, v);
for(int i = 1;i <= q; i++) {
int x, y, cost;
std::cin >> x >> y >> cost;
event[x].push_back({y, cost});
}
SpecialSet myset;
divide(1, n, aint, myset);
std::cout << myset.extract(n);
return 0;
}
Compilation message
constellation3.cpp: In function 'void divide(int, int, SegmentTree&, SpecialSet&)':
constellation3.cpp:103:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
103 | for(int h = 0; h < event[from].size(); h++)
| ~~^~~~~~~~~~~~~~~~~~~~
constellation3.cpp:106:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
106 | for(int h = 0; h < event[from].size(); h++)
| ~~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
