#include <bits/stdc++.h>
#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif
using namespace std;
const int SZ=1<<18;
vector<int> adj[200001], U[200001], P;
vector<pair<int,int>> Q[200001];
int node_cnt, L[200002][18], R[200002][18], A[200002], numL[200002], numR[200002], LR[200002], RR[200002], tree[2*SZ];
long long Ltree[2*SZ], Rtree[2*SZ], LD[200002], RD[200002];
void set_tree(int n, int v) {for(tree[n+=SZ]=v;n>>=1;) tree[n]=max(tree[2*n],tree[2*n+1]);}
void set_tree(long long *tree, int s, int e, long long v)
{
for(s+=SZ,e+=SZ;s<=e;s>>=1,e>>=1) {
if(s&1) tree[s++]+=v;
if(~e&1) tree[e--]+=v;
}
}
void dfs(int c, int *num, int *R)
{
num[c]=++node_cnt;
for(auto n: adj[c]) dfs(n,num,R);
R[c]=node_cnt;
}
int get_lpos(int v)
{
int bit=1, s=0, e=SZ-1;
while(s<e) {
int m=(s+e)>>1;
if(tree[2*bit+1]>=v) tie(bit,s)=make_pair(2*bit+1,m+1);
else tie(bit,e)=make_pair(2*bit,m);
}
return s;
}
int get_rpos(int v)
{
int bit=1, s=0, e=SZ-1;
while(s<e) {
int m=(s+e)>>1;
if(tree[2*bit]>=v) tie(bit,e)=make_pair(2*bit,m);
else tie(bit,s)=make_pair(2*bit+1,m+1);
}
return s;
}
int get_max(int s, int e)
{
int ret=-1;
for(s+=SZ,e+=SZ;s<=e;s>>=1,e>>=1) {
if(s&1) ret=max(ret,tree[s++]);
if(~e&1) ret=max(ret,tree[e--]);
}
return ret;
}
void get_mp(int n1, int n2, int v, int bit=1, int s=0, int e=SZ-1)
{
int m=(s+e)>>1;
if(n2<n1 || n2<s || e<n1 || tree[bit]<v) return;
if(s==e) {
P.push_back(m);
return;
}
get_mp(n1,n2,v,2*bit,s,m);
get_mp(n1,n2,v,2*bit+1,m+1,e);
}
long long get_sum(long long *tree, int n)
{
long long ret=tree[n+=SZ];
while(n>>=1) ret+=tree[n];
return ret;
}
long long get_LD(int x)
{
if(R[x][0]-x<2) return LD[x];
long long temp=0; P.clear();
get_mp(x+1,R[x][0]-1,get_max(x+1,R[x][0]-1));
temp=LD[P[0]];
for(auto p: P) temp+=RD[p];
return LD[x]=min(LD[x],temp);
}
long long get_RD(int x)
{
if(x-L[x][0]<2) return RD[x];
long long temp=0; P.clear();
get_mp(L[x][0]+1,x-1,get_max(L[x][0]+1,x-1));
temp=LD[P[0]];
for(auto p: P) temp+=RD[p];
return RD[x]=min(RD[x],temp);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
TEST(freopen("input.txt","r",stdin));
TEST(freopen("output.txt","w",stdout));
TEST(freopen("debug.txt","w",stderr));
int N, M;
long long S=0;
cin>>N; A[0]=A[N+1]=0x7fffffff;
for(int i=1;i<=N;i++) {
cin>>A[i];
U[A[i]].push_back(i);
}
cin>>M;
for(int i=0;i<M;i++) {
int x, y, c;
cin>>x>>y>>c;
Q[y].emplace_back(x,c);
S+=c;
}
set_tree(0,A[0]);
for(int i=0;++i<=N;) {
adj[L[i][0]=get_lpos(A[i])].push_back(i);
set_tree(i,A[i]);
}
node_cnt=-1; dfs(0,numL,LR); numL[N+1]=LR[N+1]=++node_cnt;
memset(tree,0,sizeof(tree));
set_tree(N+1,A[0]); R[N+1][0]=N+1;
for(int i=N+1;--i;) {
adj[R[i][0]=get_rpos(A[i])].push_back(i);
adj[i].clear();
set_tree(i,A[i]);
}
node_cnt=-1; dfs(N+1,numR,RR); numR[0]=RR[0]=++node_cnt;
R[0][0]=N+1; L[N+1][0]=0;
for(int j=1;j<18;j++) for(int i=N+2;--i>=0;) {
L[i][j]=L[L[i][j-1]][j-1];
R[i][j]=R[R[i][j-1]][j-1];
}
for(int y=0;++y<=N;) {
for(auto[x,c]: Q[y]) {
int l=x, r=x;
long long v;
for(int j=18;--j>=0;) {
if(A[L[l][j]]<y) l=L[l][j];
if(A[R[r][j]]<y) r=R[r][j];
}
l=L[l][0]; r=R[r][0];
v=get_sum(Ltree,numL[x])+get_sum(Rtree,numR[x])-c;
LD[l]=min(LD[l],v); RD[r]=min(RD[r],v);
}
for(auto x: U[y]) {
set_tree(Ltree,numL[x],LR[x],get_RD(x));
set_tree(Rtree,numR[x],RR[x],get_LD(x));
}
}
cout<<S+get_LD(0)<<'\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
16588 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
16588 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
16588 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
