#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+6;
int n,m,sum;
struct star
{
int x,y,c;
bool operator<(star const& other)const
{
return make_pair(y,c)>make_pair(other.y,other.c);
}
};
struct DSU
{
int par[MAXN],sz[MAXN];
void init()
{
for(int i=1;i<MAXN;i++)
{
par[i]=i;sz[i]=1;
}
}
int getRoot(int u)
{
if(par[u]==u)return u;
return par[u]=getRoot(par[u]);
}
void join(int p,int q)
{
if(sz[p]>=sz[q])
{
par[q]=p;
sz[p]+=sz[q];
}
else
{
par[p]=q;
sz[q]+=sz[p];
}
}
}dsu;
struct segment_tree
{
int t[4*MAXN];
int lazy[4*MAXN];
void init()
{
memset(t,0,sizeof(t));
memset(lazy,0,sizeof(lazy));
}
void push(int l,int r,int idx)
{
t[idx]+=lazy[idx];
if(l!=r)
{
lazy[idx*2]+=lazy[idx];
lazy[idx*2+1]+=lazy[idx];
}
lazy[idx]=0;
}
void update(int l,int r,int idx,int ql,int qr,int val)
{
push(l,r,idx);
if(l>qr||r<ql)return;
if(l>=ql&&r<=qr)
{
lazy[idx]+=val;
push(l,r,idx);
return;
}
int mid=(l+r)/2;
update(l,mid,idx*2,ql,qr,val);
update(mid+1,r,idx*2+1,ql,qr,val);
t[idx]=max(t[idx*2],t[idx*2+1]);
}
int query(int l,int r,int idx,int ql,int qr)
{
push(l,r,idx);
if(l>qr||r<ql)return 0;
if(l>=ql&&r<=qr)
{
return t[idx];
}
int mid=(l+r)/2;
return max(query(l,mid,idx*2,ql,qr),query(mid+1,r,idx*2+1,ql,qr));
}
void update(int l,int r,int val)
{
update(1,n,1,l,r,val);
}
int query(int l,int r)
{
return query(1,n,1,l,r);
}
}tree;
int a[MAXN];
vector<star>starsx[MAXN];
vector<star>starsy[MAXN];
vector<int>jp[MAXN];
int pr[MAXN];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
dsu.init();tree.init();
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
if(i>1)jp[max(a[i],a[i-1])].push_back(i);
}
cin>>m;
for(int i=1;i<=m;i++)
{
int x,y,c;
cin>>x>>y>>c;sum+=c;
starsx[x].push_back({x,y,c});
}
for(int i=1;i<=n;i++)
{
vector<star>v1;
sort(starsx[i].begin(),starsx[i].end());
for(int j=0;j<starsx[i].size();j++)
{
while(!v1.size()==0&&v1.back().c<starsx[i][j].c)
{
v1.pop_back();
}
v1.push_back(starsx[i][j]);
}
for(auto xd:v1)
{
starsy[xd.y].push_back(xd);
}
}
for(int i=1;i<=n;i++)
{
for(auto xd:starsy[i])
{
tree.update(xd.x,xd.x,xd.c-pr[xd.x]);
pr[xd.x]=xd.c;
}
for(auto xd:jp[i])
{
int e1=xd,e2=xd-1;
int r1=dsu.getRoot(e1);
int r2=dsu.getRoot(e2);
int mxl=tree.query(e2-dsu.sz[r2]+1,e2);
int mxr=tree.query(e1,e1+dsu.sz[r1]-1);
tree.update(e2-dsu.sz[r2]+1,e2,mxr);
tree.update(e1,e1+dsu.sz[r1]-1,mxl);
dsu.join(r1,r2);
}
}
cout<<sum-tree.query(1,n)<<endl;
return 0;
}
Compilation message
constellation3.cpp: In function 'int main()':
constellation3.cpp:124:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<star>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
124 | for(int j=0;j<starsx[i].size();j++)
| ~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
22220 KB |
Output is correct |
| 2 |
Incorrect |
14 ms |
22256 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
22220 KB |
Output is correct |
| 2 |
Incorrect |
14 ms |
22256 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
22220 KB |
Output is correct |
| 2 |
Incorrect |
14 ms |
22256 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
