#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define f first
#define s second
const int N=2e5+1;
int c[N], x[N], y[N];
int n, m;
vector<int> xs;
int ind[N];
ll sum[N];
vector<pair<int,int>> pts;
struct segtree{
int n;
vector<pair<int,int>> mx;
segtree(){
}
void init(int n, vector<int> &v){
this->n=n;
mx.resize(4*n);
build(v, 0, 0, n);
}
void build(vector<int> &v, int x, int lx, int rx){
if(rx-lx==1){
mx[x]={v[lx],lx};
cout << "max " << lx << " "<< rx << ' ' << mx[x].f << '\n';
return;
}
int m=(lx+rx)/2;
build(v, 2*x+1, lx, m);
build(v, 2*x+2, m, rx);
mx[x]=max(mx[2*x+1], mx[2*x+2]);
}
void pull(int i, int x, int lx, int rx){
if(rx-lx==1){
mx[x]={-1e9, i};
return;
}
int m=(lx+rx)/2;
if(i<m) pull(i, 2*x+1, lx, m);
else pull(i, 2*x+2, m, rx);
mx[x]=max(mx[2*x+1], mx[2*x+2]);
}
void pull(int i){ pull(i, 0, 0, n); }
pair<int,int> get_max(int l, int r, int x, int lx, int rx){
cout << x << endl;
if(lx>=l && rx<=r) return mx[x];
if(lx>=r || rx<=l) return {-1e9, 9};
int m=(lx+rx)/2;
return max(get_max(l, r, 2*x+1, lx, m), get_max(l, r, 2*x+2, m, rx));
}
pair<int,int> get_max(int l, int r){ return r<=l?make_pair(-int(1e9), 0):get_max(l, r, 0, 0, n); }
} star, pillar;
ll ft[N];
void upd(int i, ll v){
i++;
while(i<=n){
ft[t]+=v;
i+=i&-i;
}
}
ll sum(int i){
i++;
ll ret=0;
while(i){
ret+=ft[i];
i-=i&-i;
}
}
ll sum(int l, int r){
l++; r++;
return sum(r)-sum(l-1);
}
ll solve(int l, int r){
cout << "lr " << l << " " <<r << endl;
if(r<l) return 0;
vector<int> ind;
pair<int,int> p=pillar.get_max(l, r+1);
int mx=p.f;
cout << "max! " << mx << " " << p.s << "\n";
pillar.pull(p.s);
ind.push_back(p.s);
while((p=pillar.get_max(l, r+1)).f==mx){
int j=p.s;
pillar.pull(j);
ind.push_back(j);
}
int L=lower_bound(xs.begin(), xs.end(), l)-xs.begin();
int R=upper_bound(xs.begin(), xs.end(), r)-xs.begin();
while((p=star.get_max(L, R)).f>mx){
int j=p.s;
int st=pts[j].s;
star.pull(j);
sum.upd(x[st], c[j]);
}
ll ret=1e18;
int prv=l-1;
ind.push_back(r+1);
for(int i=0; i<ind.size(); i++){
ret=min(ret, solve(prv+1, ind[i]-1));
prv=ind[i];
}
cout << "solve " << l << " "<< r <<" " << ret << "\n";
return ret;
}
int main(){
cin.tie(0)->sync_with_stdio(0);
cin >> n;
vector<int> h(n);
for(int &x:h) cin >> x;
pillar.init(n, h);
ll tot=0;
cin >> m;
vector<int> ys;
for(int i=0; i<m; i++){
cin >> x[i] >> y[i] >> c[i];
x[i]--;
xs.push_back(x[i]);
pts.push_back({x[i],i});
tot+=c[i];
}
sort(pts.begin(), pts.end());
sort(xs.begin(), xs.end());
for(auto &p:pts) p.f=y[p.s], ys.push_back(p.f);
star.init(m, ys);
cout << tot-solve(0,n-1);
}
Compilation message
constellation3.cpp: In function 'void upd(int, ll)':
constellation3.cpp:70:12: error: 't' was not declared in this scope
70 | ft[t]+=v;
| ^
constellation3.cpp: At global scope:
constellation3.cpp:75:13: error: 'll sum(int)' redeclared as different kind of entity
75 | ll sum(int i){
| ^
constellation3.cpp:13:4: note: previous declaration 'll sum [200001]'
13 | ll sum[N];
| ^~~
constellation3.cpp: In function 'll sum(int)':
constellation3.cpp:82:1: warning: no return statement in function returning non-void [-Wreturn-type]
82 | }
| ^
constellation3.cpp: At global scope:
constellation3.cpp:84:20: error: 'll sum(int, int)' redeclared as different kind of entity
84 | ll sum(int l, int r){
| ^
constellation3.cpp:13:4: note: previous declaration 'll sum [200001]'
13 | ll sum[N];
| ^~~
constellation3.cpp: In function 'll sum(int, int)':
constellation3.cpp:86:17: error: 'sum' cannot be used as a function
86 | return sum(r)-sum(l-1);
| ^
constellation3.cpp:86:26: error: 'sum' cannot be used as a function
86 | return sum(r)-sum(l-1);
| ^
constellation3.cpp: In function 'll solve(int, int)':
constellation3.cpp:111:13: error: request for member 'upd' in 'sum', which is of non-class type 'll [200001]' {aka 'long long int [200001]'}
111 | sum.upd(x[st], c[j]);
| ^~~
constellation3.cpp:118:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
118 | for(int i=0; i<ind.size(); i++){
| ~^~~~~~~~~~~
