#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],fa[maxn],mx[maxn],val2[maxn];
pair<vector<long long>,vector<long long>>fmx[maxn];
int kaf=(1<<18);
struct segment{
long long seg[(1<<19)];
void upd(int i,int w){
while(i!=0){
seg[i]+=w;
i>>=1;
}
}
long long pors(int i,int l,int r,int tl,int tr){
if(l>r||l>tr||r<tl||tl>tr){
return 0;
}
if(l>=tl&&r<=tr){
return seg[i];
}
int m=(l+r)>>1;
return pors((i<<1),l,m,tl,tr)+pors((i<<1)^1,m+1,r,tl,tr);
}
}val2f,val2s;
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]){
if(mx[i].first==allind.front().first){
fmx[i].first.push_back(allind.front().second);
}
if(mx[i].first<allind.front().first){
mx[i].first=allind.front().first;
fmx[i].first.clear();
fmx[i].first.push_back(allind.front().second);
}
allind.pop_front();
}
fa[i].first=allind.front().second;
allind.push_front(make_pair(all[i],i));
}
allind.clear();
allind.push_back(make_pair(n+1,n+1));
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]){
if(mx[i].second==allind.front().first){
fmx[i].second.push_back(allind.front().second);
}
if(mx[i].second<allind.front().first){
mx[i].second=allind.front().first;
fmx[i].second.clear();
fmx[i].second.push_back(allind.front().second);
}
allind.pop_front();
}
fa[i].second=allind.front().second;
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++){
res+=val2[i].second;
}
maxa=-1;
for(long long i=allq[ind].x;i>allq[ind].l;i--){
res+=val2[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);
mainres=max(mainres,res);
}
void upd(long long ind){
val[ind]=fakeval[ind];
long long res=0,maxa=-1;
vector<long long>v;
if(fa[ind].first!=ind-1){
v=fmx[ind].first;
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();
if(fa[ind].second!=ind+1){
v=fmx[ind].second;
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));
val2[ind].first=-val2f.pors(1,0,kaf-1,fa[ind].first+1,ind-1);
// for(int i=ind-1;i>fa[ind].first;i--){
// val2[ind].first-=val2[i].first;
// }
val2[ind].first+=val[ind].first;
val2f.upd(ind+kaf,val2[ind].first);
val2[ind].second=-val2s.pors(1,0,kaf-1,ind+1,fa[ind].second-1);
// for(int i=ind+1;i<fa[ind].second;i++){
// val2[ind].second-=val2[i].second;
// }
val2[ind].second+=val[ind].second;
val2s.upd(ind+kaf,val2[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";
}
Compilation message
constellation3.cpp: In function 'void updn(long long int)':
constellation3.cpp:94:12: warning: variable 'maxa' set but not used [-Wunused-but-set-variable]
94 | long long maxa=-1;
| ^~~~
constellation3.cpp: In function 'void upd(long long int)':
constellation3.cpp:110:18: warning: variable 'maxa' set but not used [-Wunused-but-set-variable]
110 | long long res=0,maxa=-1;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
33112 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
33112 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
33112 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
33112 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
33112 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
33112 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
