#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
#define ll long long
const int mxn=2e5+5;
ll n,m,a[mxn],par[mxn],sz[mxn],rast[mxn],chap[mxn],mxr[mxn],mxl[mxn],mark[mxn],rb[mxn],lb[mxn];
ll dp[mxn],ans=0;
struct star{
int xx,yy,c;
}str[mxn];
vector<pair<int,int> >bld;
pair<ll,ll>pd[mxn];
bool cmp(star x,star y){
if(x.yy!=y.yy)
return x.yy<y.yy;
return x.xx<y.xx;
}
struct segment{
ll val[mxn*4];
void up(int id,int L,int R,int l,ll x){
if(L+1==R){
val[id]=x;
return;
}
int mid=(L+R)/2;
if(l<mid)
up(id*2,L,mid,l,x);
else
up(id*2+1,mid,R,l,x);
val[id]=val[id*2]+val[id*2+1];
}
ll get(int id,int L,int R,ll l,ll r){
if(L==l && R==r)
return val[id];
ll mid=(L+R)/2,res=0;
if(l<mid)
res+=get(id*2,L,mid,l,min(r,mid));
if(r>mid)
res+=get(id*2+1,mid,R,max(l,mid),r);
return res;
}
}seg[2];
int fndpar(int x){
return (par[x]==0?x:par[x]=fndpar(par[x]));
}
void dsu(int x,int y){
if(x==y)return;
int L=min(chap[x],chap[y]),R=max(rast[x],rast[y]);
int l=(a[mxl[x]]<a[mxl[y]])?mxl[y]:mxl[x];
int r=(a[mxr[x]]>a[mxr[y]])?mxr[x]:mxr[y];
if(sz[x]<sz[y])swap(x,y);
sz[x]+=sz[y];
par[y]=x;
mxl[x]=l;
mxr[x]=r;
chap[x]=L;
rast[x]=R;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
bld.push_back({a[i],i});
chap[i]=rast[i]=i;
mxr[i]=mxl[i]=i;
}
a[n+1]=n+1;
a[0]=n+2;
bld.push_back({n+1,n+1});
chap[n+1]=rast[n+1]=n+1;
mxr[n+1]=mxl[n+1]=n+1;
cin>>m;
for(int i=1;i<=m;i++){
cin>>str[i].xx>>str[i].yy>>str[i].c;
ans+=str[i].c;
}
sort(bld.begin(),bld.end());
sort(str+1,str+m+1,cmp);
int p=1;
/////0=sc=rast ,fr=1=chap
for(int i=0;i<=n;i++){
while(p<=m && str[p].yy<=bld[i].fr){
int x=fndpar(str[p].xx);
ll w1=seg[0].get(1,1,n+2,str[p].xx,rast[x]+1);
ll w2=seg[1].get(1,1,n+2,chap[x],str[p].xx+1);
dp[p]=str[p].c+w1+w2;
if(a[chap[x]-1]<a[rast[x]+1])
rb[chap[x]-1]=max(rb[chap[x]-1],dp[p]);
else
lb[rast[x]+1]=max(lb[rast[x]+1],dp[p]);
p++;
}
int x1=(mark[bld[i].sc+1])?fndpar(bld[i].sc+1):bld[i].sc;
int x2=(mark[bld[i].sc-1])?fndpar(bld[i].sc-1):bld[i].sc;
//cout<<mxr[x1]<<" "<<rast[x1]<<" "<<chap[x2]<<" "<<mxl[x2]<<endl;
ll z1=seg[1].get(1,1,n+2,bld[i].sc,mxr[x1]+1)+seg[0].get(1,1,n+2,mxr[x1],rast[x1]+1);
ll z2=seg[0].get(1,1,n+2,mxl[x2],bld[i].sc+1)+seg[1].get(1,1,n+2,chap[x2],mxl[x2]+1);
ll q1=seg[0].get(1,1,n+2,bld[i].sc,rast[x1]+1);
ll q2=seg[1].get(1,1,n+2,chap[x2],bld[i].sc+1);
//cout<<z2<<endl;
pd[bld[i].sc].fr=max(z2,lb[bld[i].sc])-q2;
pd[bld[i].sc].sc=max(z1,rb[bld[i].sc])-q1;
seg[0].up(1,1,n+2,bld[i].sc,pd[bld[i].sc].sc);
seg[1].up(1,1,n+2,bld[i].sc,pd[bld[i].sc].fr);
dsu(x2,bld[i].sc);
dsu(fndpar(bld[i].sc),x1);
mark[bld[i].sc]=1;
//cout<<bld[i].sc<<" "<<pd[bld[i].sc].fr<<" "<<pd[bld[i].sc].sc<<endl;
}
cout<<ans-seg[1].get(1,1,n+2,1,n+2);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
16728 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
16728 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
16728 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
