#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
using namespace std;
using lint = long long;
using vint = vector<int>;
using pii = pair<int,int>;
using pil = pair<int,lint>;
const int MAX_N=200010;
struct Setobj
{
set<pil> s;
lint cshift;
Setobj()
{
s.insert({0,0});
cshift=0;
}
void push_star(int h,lint c)
{
cshift+=c;
pil o={h,-c};
auto it=s.upper_bound(o);
if(it!=s.begin() && prev(it)->second<=o.second)return;
while(it!=s.end() && it->second>=o.second)
{
auto del=it++;
s.erase(del);
}
s.insert(o);
}
void merge_(const Setobj &so,int h1,int h2)
{
lint cs1=cshift+so.cshift,cs2=cs1;
if(h1<h2)
{
cs1+=so.s.begin()->second;
cs2+=prev(s.lower_bound({h2,0}))->second;
}
if(h1>h2)
{
cs1+=prev(so.s.lower_bound({h1,0}))->second;
cs2+=s.begin()->second;
}
for(auto o : so.s)
{
o.second+=cs2-cs1;
auto it=s.upper_bound(o);
if(it!=s.begin() && prev(it)->second<=o.second)continue;
while(it!=s.end() && it->second>=o.second)
{
auto del=it++;
s.erase(del);
}
s.insert(o);
}
cshift=cs1;
}
lint value()
{
return cshift+prev(s.end())->second;
}
};
int n,m;
int arr[MAX_N],l[MAX_N],r[MAX_N];
pii sorth[MAX_N];
int seti[MAX_N];
Setobj st[MAX_N];
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin >> n;
for(int i=1;i<=n;i++)
{
cin >> arr[i];
sorth[i]={arr[i],i};
seti[i]=i;
}
sort(sorth+1,sorth+1+n);
vector<pii> mxh={{0,MAX_N}};
arr[0]=arr[n+1]=MAX_N;
for(int i=1;i<=n;i++)
{
while(mxh.back().second<=arr[i])mxh.pop_back();
l[i]=mxh.back().first;
mxh.push_back({i,arr[i]});
}
mxh={{n+1,MAX_N}};
for(int i=n;i>=1;i--)
{
while(mxh.back().second<arr[i])mxh.pop_back();
r[i]=mxh.back().first;
if(arr[i]!=mxh.back().second)
mxh.push_back({i,arr[i]});
}
cin >> m;
for(int i=0;i<m;i++)
{
int x,y,c;
cin >> x >> y >> c;
if(arr[r[x]]==arr[x])x=r[x];
st[x].push_star(y,c);
}
for(int i=1;i<n;i++)
{
int u=sorth[i].second,v;
if(st[seti[u]].s.size()==1)continue;
if(arr[l[u]]<arr[r[u]])
{
v=l[u];
if(arr[r[v]]<=arr[r[u]])r[v]=r[u];
}
else
{
v=r[u];
if(arr[l[v]]<=arr[l[u]])l[v]=l[u];
}
//if(st[seti[u]].s.size()<st[seti[v]].s.size())swap(u,v);
st[seti[u]].merge_(st[seti[v]],arr[u],arr[v]);
seti[v]=seti[u];
}
cout << st[seti[sorth[n].second]].value();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
27544 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
27544 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
27544 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
