#include<bits/stdc++.h>
using namespace std;
const int maxn=200000+10;
struct node{
int x,y,w,l,r;
}allq[maxn];
int all[maxn],q,n;
vector<int>sn,si;
pair<long long,long long>val[maxn],fakeval[maxn];
bool cmpn(int a,int b){
return allq[a].y<allq[b].y;
}
bool cmpi(int a,int b){
return all[a]<all[b];
}
void callr()
{
for(int i=1;i<=q;i++){
int l=allq[i].x,r=allq[i].x;
while(l!=0&&all[l]<allq[i].y){
l--;
}
while(r!=n+1&&all[r]<allq[i].y){
r++;
}
allq[i].l=l;
allq[i].r=r;
}
}
long long mainres=0;
void updn(int ind){
long long res=0,resa=0;
for(int i=allq[ind].x;i<allq[ind].r;i++){
res=max(res,val[i].second);
}
for(int i=allq[ind].x;i>allq[ind].l;i--){
resa=max(resa,val[i].first);
}
res+=resa+allq[ind].w;
fakeval[allq[ind].r].first=max(fakeval[allq[ind].r].first,res);
fakeval[allq[ind].l].second=max(fakeval[allq[ind].l].second,res);
// cout<<ind<<" "<<allq[ind].l<<" "<<allq[ind].r<<" "<<res<<"\n";
mainres=max(mainres,res);
}
void upd(int ind){
val[ind]=fakeval[ind];
// cout<<ind<<" "<<val[ind].first<<" "<<val[ind].second<<"\n";
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>all[i];
si.push_back(i);
}
cin>>q;
long long suma=0;
for(int i=1;i<=q;i++){
sn.push_back(i);
cin>>allq[i].x>>allq[i].y>>allq[i].w;
suma+=allq[i].w;
}
callr();
sort(sn.begin(),sn.end(),cmpn);
sort(si.begin(),si.end(),cmpi);
int i=0,j=0;
while(i<(int)sn.size()&&j<(int)si.size()){
if(allq[sn[i]].y<=all[si[j]]){
updn(sn[i]);
i++;
}
else{
upd(si[j]);
j++;
}
}
while(i<(int)sn.size()){
updn(sn[i]);
i++;
}
while(j<(int)si.size()){
upd(si[j]);
j++;
}
int now=(int)si.size()-1;
long long res=val[si[now]].second;
while(now!=0&&all[si[now-1]]==all[si[now]]){
now--;
res+=val[si[now]].second;
}
res+=val[si[now]].first;
mainres=max(mainres,res);
mainres=suma-mainres;
cout<<mainres<<"\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
6492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
6492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
6492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
