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