#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5;
const int G = 2*N;
const int logN = 20;
int n,m;
vector <int> e[G];
int v[N];
vector <int> lefte[N + 1];
vector <int> righte[N + 1];
int prleft[N + 1][logN],prright[N + 1][logN];
int subleft[N + 1],subright[N + 1];
int leftside[N + 1],rightside[N + 1];
///bear your fangs its time to fight
///pa pa pa parade in shame tonight
int ordleft[N + 1],ordright[N + 1];
int ord2left[N + 1],ord2right[N + 1];
int cntleft = 0,cntright = 0;
int leftid[N],rightid[N];
int fenleft[N + 1],fenright[N + 1];
///
int stk[N];
vector <int> p;
struct star{
int x,y,c;
}v2[N];
vector <int> cand[G];
map<int,pair<int,int>> f;
vector <int> points;
ll dp[G];
int cnt = 0;
void addedge(int u,int w){
e[u].push_back(w);
}
void addleft(int pos,int nr){
for(int i = pos;i <= n;i|=(i + 1)){
fenleft[i]+=nr;
}
}
void addright(int pos,int nr){
for(int i = pos;i <= n;i|=(i + 1)){
fenright[i]+=nr;
}
}
ll getleft(int pos){
ll r = 0;
for(int i = pos;i >= 0;i&=(i + 1),i--){
r+=fenleft[i];
}
return r;
}
ll getright(int pos){
ll r = 0;
for(int i = pos;i >= 0;i&=(i + 1),i--){
r+=fenright[i];
}
return r;
}
void dfs(int node){
ll mx = 0;
for(auto i:e[node]){
dfs(i);
mx+=dp[i];
}
for(auto i:cand[node]){
///leftadd
star s = v2[i];
ll candcost = s.c;
int j = s.x;
candcost+=getright(ordright[j]);
for(int k = logN - 1;k >= 0;k--){
if(v[prright[j][k]] < s.y && prright[j][k] != n){
j = prright[j][k];
}
}
j = prright[j][0];
candcost-=getright(ordright[j]);
j = s.x;
candcost+=getleft(ordleft[j]);
for(int k = logN - 1;k >= 0;k--){
if(v[prleft[j][k]] < s.y && prleft[j][k] != n){
j = prleft[j][k];
}
}
j = prleft[j][0];
candcost-=getleft(ordleft[j]);
mx = max(mx,candcost);
}
dp[node] = mx;
if(ord2left[node] != -1){
addleft(ordleft[ord2left[node]],dp[node]);
addleft(ordleft[ord2left[node]] + subleft[ord2left[node]],-dp[node]);
}
if(ord2right[node] != -1){
addright(ordright[ord2right[node]],dp[node]);
addright(ordright[ord2right[node]] + subright[ord2right[node]],-dp[node]);
}
}
void dfsleft(int node, int p){
prleft[node][0] = p;
subleft[node] = 1;
ordleft[node] = cntleft++;
for(auto i:lefte[node]){
dfsleft(i, node);
subleft[node]+=subleft[i];
}
}
void dfsright(int node, int p){
prright[node][0] = p;
subright[node] = 1;
ordright[node] = cntright++;
for(auto i:righte[node]){
dfsright(i, node);
subright[node]+=subright[i];
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin>>n;
p.resize(n);
for(int i = 0;i < n;i++){
cin>>v[i];
p[i] = i;
leftid[i] = rightid[i] = -1;
}
sort(p.begin(),p.end(),[&](int a,int b){
if(v[a] == v[b])return a < b;
return v[a] > v[b];
});
cin>>m;
ll sum = 0;
for(int i = 0;i < m;i++){
cin>>v2[i].x>>v2[i].y>>v2[i].c;
sum+=v2[i].c;
v2[i].x--;
}
sort(v2,v2 + m,[&](star a,star b){
return a.y > b.y;
});
f[0] = {n - 1,cnt++};
int pt = 0;
int pt2 = 0;
for(int i = n;i >= 1;i--){
points.clear();
while(pt2 < n && v[p[pt2]] >= i){
points.push_back(p[pt2]);
pt2++;
}
int j = 0;
while(j < points.size()){
auto it = prev(f.upper_bound(points[j]));
int k = j;
while(k < points.size() && points[k] <= it->second.first){
k++;
}
int l = it->first;
int r = it->second.first;
int id = it->second.second;
f.erase(it);
for(int p = j;p <= k;p++){
int lside = (p == j?l:points[p - 1] + 1);
int rside = (p == k?r:points[p] - 1);
if(lside <= rside){
addedge(id,cnt);
f[lside] = {rside,cnt};
ord2left[cnt] = ord2right[cnt] = -1;
if(p != k){
leftid[rside + 1] = cnt;
ord2left[cnt] = rside + 1;
}
if(p != j){
rightid[lside - 1] = cnt;
ord2right[cnt] = lside - 1;
}
cnt++;
}
}
j = k;
}
while(pt < m && v2[pt].y >= i){
int id = prev(f.upper_bound(v2[pt].x))->second.second;
cand[id].push_back(pt);
pt++;
}
}
int cnt2 = 0;
for(int i = 0;i < n;i++){
while(cnt2 > 0 && v[i] > v[stk[cnt2 - 1]]){
cnt2--;
}
leftside[i] = (cnt2 == 0?n:stk[cnt2 - 1]);
lefte[leftside[i]].push_back(i);
stk[cnt2++] = i;
}
cnt2 = 0;
for(int i = n - 1;i >= 0;i--){
while(cnt2 > 0 && v[i] > v[stk[cnt2 - 1]]){
cnt2--;
}
rightside[i] = (cnt2 == 0?n:stk[cnt2 - 1]);
righte[rightside[i]].push_back(i);
stk[cnt2++] = i;
}
dfsleft(n, n);
dfsright(n, n);
for(int j = 1;j < logN;j++){
for(int i = 0;i <= n;i++){
prleft[i][j] = prleft[prleft[i][j - 1]][j - 1];
prright[i][j] = prright[prright[i][j - 1]][j - 1];
}
}
dfs(0);
cout<<sum - dp[0];
return 0;
}
Compilation message
constellation3.cpp: In function 'int main()':
constellation3.cpp:152:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
152 | while(j < points.size()){
| ~~^~~~~~~~~~~~~~~
constellation3.cpp:155:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
155 | while(k < points.size() && points[k] <= it->second.first){
| ~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
47452 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
47452 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
47452 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
47452 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
47452 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
47452 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
