#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 1e5+1, oo = 1e9;
struct el {
int y,c;
ll mydp;
bool operator<(const el& o ) const {
return y>o.y;
}
};
struct DS {
ll lazy=0, mn = 0;
// mn is min dp value inside this DS.
// sum is the sum of the currently "bad" stars.
priority_queue<el> pq;
void add(int y, int c, ll mydp=0) {
lazy+=c;
pq.push({y,c,mydp+mn-lazy});
mn+=c;
}
void clean(int h) {
// everything below h is safe.
while(!pq.empty() and pq.top().y<=h) {
mn = min(mn,lazy+pq.top().mydp);
pq.pop();
}
}
int size() {
return pq.size();
}
};
void merge(DS& a, DS& b) {
if(a.size()<b.size()) swap(a,b);
a.lazy+=b.mn;
while(b.size()) {
auto e = b.pq.top();
e.mydp+=b.lazy;
a.add(e.y,e.c,e.mydp);
b.pq.pop();
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n; cin >> n;
vi a(n);
for(auto& i : a) cin >> i;
vector<basic_string<int>> adj(n);
int root=-1;
{
vi l(n);
for(int i=0;i<n;++i) {
l[i] = i-1;
while(l[i]>=0 and a[l[i]]<a[i]) {
l[i] = l[l[i]];
}
}
vi r(n);
for(int i=n-1;i>=0;--i) {
r[i] = i+1;
while(r[i]<n and a[r[i]]<=a[i]) {
r[i]=r[r[i]];
}
}
for(int i=0;i<n;++i) {
if(l[i]<0 and r[i]>=n) root=i;
else if(r[i]<n and (l[i]<0 or a[l[i]]>a[r[i]])) adj[r[i]].push_back(i);
else adj[l[i]].push_back(i);
}
}
vector<vector<pi>> stars(n);
int m; cin >> m;
while(m--) {
int x,y,c; cin >> x >> y >> c;
--x;
stars[x].push_back({y,c});
}
vector<DS> ds(n);
auto dfs = [&](auto&& self, int at) -> void {
for(auto [y,c] : stars[at]) {
ds[at].add(y,c);
}
for(int to : adj[at]) {
self(self,to);
ds[to].clean(a[at]);
merge(ds[at],ds[to]);
}
};
dfs(dfs,root);
auto& dsr = ds[root];
ll ans=dsr.mn;
while(dsr.size()) {
auto e = dsr.pq.top();
dsr.pq.pop();
ans=min(ans,e.mydp + dsr.lazy);
}
cout << ans << '\n';
}
Compilation message
constellation3.cpp: In lambda function:
constellation3.cpp:92:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
92 | for(auto [y,c] : stars[at]) {
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
