#include<bits/stdc++.h>
using namespace std;
const int N = 2e5;
const int G = 2*N;
int n,m;
vector <int> e[G];
int v[N];
int leftid[N],rightid[N];
int leftside[N + 1],rightside[N + 1];
///
int stk[N];
vector <int> p;
struct star{
int x,y,c;
}v2[N];
vector <int> cand[G];
map<int,pair<int,int>> f;
int dp[G];
int cnt = 1;
void addedge(int u,int w){
e[u].push_back(w);
}
void dfs(int node){
//cout<<node<<'\n';
int mx = 0;
for(auto i:e[node]){
dfs(i);
//cout<<node<<' '<<i<<'\n';
mx+=dp[i];
}
for(auto i:cand[node]){
///leftadd
star s = v2[i];
int candcost = s.c;
//cout<<"starcheck:"<<' '<<node<<' '<<s.x<<' '<<s.y<<'\n';
for(int j = s.x;j != n && v[j] < s.y;j = rightside[j]){
candcost+=dp[rightid[j]];
//cout<<rightid[j]<<' ';
}
for(int j = s.x;j != n && v[j] < s.y;j = leftside[j]){
candcost+=dp[leftid[j]];
//cout<<leftid[j]<<' ';
}
//cout<<'\n';
mx = max(mx,candcost);
}
dp[node] = mx;
}
int main(){
cin>>n;
p.resize(n);
for(int i = 0;i < n;i++){
cin>>v[i];
p[i] = i;
}
sort(p.begin(),p.end(),[&](int a,int b){
return v[a] > v[b];
});
cin>>m;
int sum = 0;
for(int i = 0;i < m;i++){
cin>>v2[i].x>>v2[i].y>>v2[i].c;
sum+=v2[i].c;
v2[i].x--;
}
sort(v2,v2 + m,[&](star a,star b){
return a.y > b.y;
});
addedge(0,cnt);
f[0] = {n - 1,cnt++};
int pt = 0;
for(auto i:p){
///????
while(pt < m && v2[pt].y > v[i]){
int id = prev(f.upper_bound(v2[pt].x))->second.second;
cand[id].push_back(pt);
pt++;
}
auto it = prev(f.upper_bound(i));
int l = it->first;
int r = it->second.first;
int id = it->second.second;
if(l < i){
f[l] = {i - 1,cnt++};
addedge(id, cnt - 1);
leftid[i] = cnt - 1;
}
if(i < r){
f[i + 1] = {r,cnt++};
addedge(id, cnt - 1);
rightid[i] = cnt - 1;
}
}
int cnt2 = 0;
for(int i = 0;i < n;i++){
while(cnt2 > 0 && v[i] > v[stk[cnt2 - 1]]){
cnt2--;
}
leftside[i] = (cnt2 == 0?n:stk[cnt2 - 1]);
stk[cnt2++] = i;
}
cnt2 = 0;
for(int i = n - 1;i >= 0;i--){
while(cnt2 > 0 && v[i] > v[stk[cnt2 - 1]]){
cnt2--;
}
rightside[i] = (cnt2 == 0?n:stk[cnt2 - 1]);
stk[cnt2++] = i;
}
dfs(0);
cout<<sum - dp[0];
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
27480 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
27480 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
27480 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
