#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ii pair<int,int>
#define fi first
#define se second
const int mxn = 2e5+5;
int n,m;
ll tree[mxn*4];
int h[mxn],pre[mxn],nxt[mxn];
struct star{
int c,r;
ll val;
bool operator < (const star &rhs)const{
return r>rhs.r;
}
};
star stars[mxn];
vector<int>ind[mxn]; //keeping ind
ll query(int pos, int id, int le, int ri){
if(le==ri){
return tree[id];
}
int mid=(le+ri)>>1;
ll res = 0ll;
if(le<=pos&&pos<=ri)res+=tree[id];
if(pos<=mid)res += query(pos,id*2,le,mid);
else res+=query(pos,id*2+1,mid+1,ri);
return res;
}
void upd(int x, int y, ll v, int id, int le, int ri){
if(x>ri||le>y)return;
if(x<=le&&ri<=y){
tree[id]+=v;
return;
}
int mid=(le+ri)>>1;
upd(x,y,v,id*2,le,mid);
upd(x,y,v,id*2+1,mid+1,ri);
return;
}
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin>>n;
for(int i=1; i<=n; i++){
cin>>h[i];
h[i]=n-h[i];
}
ll ans = 0ll;
h[0]=h[n+1]=0;
cin>>m;
for(int i=0; i<m; i++){
int c,r; ll v;
cin>>c>>r>>v;
ans += v;
r = n-r+1;
stars[i]={c,r,v};
}
sort(stars,stars+m);
for(int i=0; i<m; i++)
ind[stars[i].c].emplace_back(i);
vector<int>h_ind;
set<ii>ss;
h_ind.push_back(n+1);
ss.insert(ii(h[n+1],n+1));
for(int i=n; i>=1; i--){
while(!h_ind.empty()&&h[h_ind.back()]>=h[i]){
ss.erase({h_ind.back(),h[h_ind.back()]});
h_ind.pop_back();
}
/*
cerr<<i<<": af \n";
for(int j:h_ind)cerr<<j<<" ";
cerr<<"\n";
for(ii x:ss)cerr<<x.fi<<" "<<x.se<<"\n";
cerr<<"\n";
*/
for(int j:ind[i]){
auto it = ss.lower_bound({stars[j].r,-1});
it = prev(it);
//cerr<<j<<" "<<stars[j].r<<" "<<it->fi<<" "<<it->se<<"\n";
nxt[j]=it->se-1;
//cerr<<j<<" ... "<<nxt[j]<<"\n";
}
ss.emplace(h[i],i);
h_ind.emplace_back(i);
}
ss=set<ii>();
h_ind=vector<int>();
h_ind.push_back(0);
ss.insert(ii(h[0],0));
for(int i=1; i<=n; i++){
while(!h_ind.empty()&&h[h_ind.back()]>=h[i]){
ss.erase({h_ind.back(),h[h_ind.back()]});
h_ind.pop_back();
}
for(int j:ind[i]){
auto it = ss.lower_bound({stars[j].r,-1});
it=prev(it);
pre[j]=it->se+1;
}
ss.emplace(h[i],i);
h_ind.emplace_back(i);
}
/*
for(int i=0; i<m; i++){
cerr<<stars[i].c<<" "<<stars[i].r<<" "<<stars[i].val<<" "<<pre[i]<<" "<<nxt[i]<<"\n";
}
*/
for(int i=0; i<m; i++){
ll val = stars[i].val-query(stars[i].c,1,1,n);
//cerr<<i<<" "<<stars[i].c<<": "<<val<<" "<<stars[i].val<<"\n";
if(val>0){
ans -= val;
//cerr<<"upd "<<pre[i]<<" "<<nxt[i]<<"\n";
upd(pre[i],nxt[i],val,1,1,n);
}
}
cout<<ans<<endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
5248 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
5248 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
5248 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
