#include <bits/stdc++.h>
using namespace std;
typedef pair<long long, long long> ii;
long long H[200005];
priority_queue<ii, vector<ii>, greater<ii> > pq[200005]; ///offset applied
long long offset[200005];
long long anything[200005]; ///no offset applied
int p[200005];
int findSet(int u){
if(u == p[u])return p[u];
else{
p[u] = findSet(p[u]);
return p[u];
}
}
void unionSet(int u, int v){
u = findSet(u); v = findSet(v);
/*
if(pq[u].size() > pq[v].size()){
swap(pq[u],pq[v]);
swap(offset[u],offset[v]);
swap(anything[u],anything[v]);
}
*/
offset[v] += anything[u];
///push the things from pq[u] to pq[v];
while(!pq[u].empty()){
ii x = pq[u].top();
pq[u].pop();
x.second += offset[u];
x.second += anything[v];
x.second -= offset[v];
pq[v].push(x);
}
p[u] = v;
anything[v] = max(anything[v], anything[u]);
}
int main(){
//freopen("i.txt","r",stdin);
ios_base::sync_with_stdio(false);
cin.tie(0);
int n; cin >> n;
int order[n];
long long total = 0;
for(int i = 0;i < n;i++){
cin >> H[i];
order[i] = i;
}
int m; cin >> m;
for(int i = 0;i < m;i++){
int x, y, c; cin >> x >> y >> c;
x--;
pq[x].push(ii(y,c));
total += (long long) c;
}
for(int i = 0;i < n;i++) p[i] = i;
sort(order, order + n, [&](int a, int b){ return H[a] < H[b]; });
for(int i : order){
/*
cout << i << ":\n";
for(int j = 0;j < n;j++) cout << findSet(j) << " "; cout << endl;
for(int j = 0;j < n;j++) cout << anything[j] << " "; cout << endl;
for(int j = 0;j < n;j++) cout << offset[j] << " "; cout << endl;
for(int j = 0;j < n;j++){
vector<ii> v;
cout << j << ": ";
while(!pq[j].empty()){
v.push_back(pq[j].top());
pq[j].pop();
}
for(ii x : v){
cout << "(" << x.first << ", " << x.second + offset[j] << ") ";
pq[j].push(x);
}
cout << "\n";
}
*/
if(i != 0 && H[i-1] <= H[i]){
int u = findSet(i-1); int v = findSet(i);
if(u != v){
while(!pq[u].empty()){
ii x = pq[u].top();
if(x.first > H[i]) break;
pq[u].pop();
anything[u] = max(anything[u], x.second + offset[u]);
//if(i == 5) cout << anything[u] << "G\n";
}
unionSet(u,v);
}
}
//cout << anything[i] << "A\n";
if(i != n-1 && H[i+1] <= H[i]){
int u = findSet(i+1); int v = findSet(i);
if(u != v){
while(!pq[u].empty()){
ii x = pq[u].top();
if(x.first > H[i]) break;
pq[u].pop();
anything[u] = max(anything[u], x.second + offset[u]);
//if(i == 5) cout << anything[u] << "G\n";
}
unionSet(u,v);
}
}
}
/*
cout << "end:\n";
for(int j = 0;j < n;j++) cout << findSet(j) << " "; cout << endl;
for(int j = 0;j < n;j++) cout << anything[j] << " "; cout << endl;
for(int j = 0;j < n;j++) cout << offset[j] << " "; cout << endl;
for(int j = 0;j < n;j++){
cout << j << ": ";
vector<ii> v;
while(!pq[j].empty()){
v.push_back(pq[j].top());
pq[j].pop();
}
for(ii x : v){
cout << "(" << x.first << ", " << x.second + offset[j] << ") ";
pq[j].push(x);
}
cout << "\n";
}
*/
int last = order[n-1];
long long ans = anything[last];
while(!pq[last].empty()){
ans = max(ans, pq[last].top().second + offset[last]);
pq[last].pop();
}
ans = max(ans, offset[last]);
cout << total - ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
6656 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
6656 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
6656 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
