#include <bits/stdc++.h>
using namespace std ;
const int MAX = 2e5 + 10 ;
int arr[MAX] ;
int n , m ;
vector< pair<int , int> >vp[MAX] ;
long long maxdp[MAX] ;
long long Max = 0 ;
int L[MAX] , R[MAX] ;
void solve(int l , int r)
{
if(l > r)
return ;
int idx = -1 ;
for(int i = l , j = r ; i <= j ; ++i , --j)
{
if(L[i] <= l && R[i] >= r)
{
idx = i ;
break ;
}
if(L[j] <= l && R[j] >= r)
{
idx = j ;
break ;
}
}
assert(idx != -1) ;
long long curMax = 0 ;
for(int i = 1 ; i <= n ; ++i)
{
if(i >= l && i <= r)
continue ;
curMax = max(curMax , maxdp[i]) ;
}
for(int i = l ; i <= r ; ++i)
{
while(vp[i].size() && vp[i].back().first <= arr[idx])
{
pair<int , int>p = vp[i].back() ;
vp[i].pop_back() ;
maxdp[i] = max(maxdp[i] , curMax + p.second) ;
Max = max(Max , maxdp[i]) ;
}
}
solve(l , idx-1) , solve(idx+1 , r) ;
}
int main()
{
ios_base::sync_with_stdio(0) ;
cin.tie(0) ;
cin>>n ;
for(int i = 1 ; i <= n ; ++i)
cin>>arr[i] , arr[i] = n-arr[i] ;
cin>>m ;
long long ans = 0 ;
for(int i = 0 ; i < m ; ++i)
{
int i2 , j2 , x ;
cin>>i2>>j2>>x ;
vp[i2].emplace_back(n-j2+1 , x) ;
ans += x ;
}
for(int i = 1 ; i <= n ; ++i)
sort(vp[i].begin() , vp[i].end()) , reverse(vp[i].begin() , vp[i].end()) ;
stack<int>s ;
for(int i = 1 ; i <= n ; ++i)
{
L[i] = 1 ;
while(s.size() && arr[i] < arr[s.top()])
s.pop() ;
if(s.size())
L[i] = s.top() + 1 ;
s.push(i) ;
}
while(s.size())
s.pop() ;
for(int i = n ; i >= 1 ; --i)
{
R[i] = n ;
while(s.size() && arr[i] <= arr[s.top()])
s.pop() ;
if(s.size())
R[i] = s.top() - 1 ;
s.push(i) ;
}
solve(1 , n) ;
ans -= Max ;
return cout<<ans<<"\n" , 0 ;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
