#include <bits/stdc++.h>
#define int long long
using namespace std;
struct star {
int i, j, c;
};
struct SegTree {
struct node {
long long maxx, lazy;
int leftSon, rightSon;
};
int root, lst, rst;
vector<node> segTree;
int newNode() {
int v = segTree.size();
segTree.push_back( { 0, 0, -1, -1 } );
return v;
}
void init( int l, int r ) {
lst = l;
rst = r;
root = newNode();
}
void propag( int v, int l, int r ) {
segTree[v].maxx += segTree[v].lazy;
if ( l != r ) {
if ( segTree[v].leftSon == -1 )
segTree[v].leftSon = newNode();
segTree[segTree[v].leftSon].lazy += segTree[v].lazy;
if ( segTree[v].rightSon == -1 )
segTree[v].rightSon = newNode();
segTree[segTree[v].rightSon].lazy += segTree[v].lazy;
}
segTree[v].lazy = 0;
}
void updatePoint( int v, int l, int r, int p, long long x ) {
propag( v, l, r );
if ( l > p || r < p )
return;
if ( l == r ) {
segTree[v].maxx = max( segTree[v].maxx, x );
return;
}
int mid = (l + r) / 2;
if ( segTree[v].leftSon == -1 )
segTree[v].leftSon = newNode();
updatePoint( segTree[v].leftSon, l, mid, p, x );
if ( segTree[v].leftSon == -1 )
segTree[v].leftSon = newNode();
updatePoint( segTree[v].rightSon, mid + 1, r, p, x );
segTree[v].maxx = max( segTree[segTree[v].leftSon].maxx, segTree[segTree[v].rightSon].maxx );
}
void updatePoint( int p, long long x ) {
updatePoint( root, lst, rst, p, x );
}
void updateInterval( int v, int l, int r, int lu, int ru, long long x ) {
propag( v, l, r );
if ( l > ru || r < lu )
return;
if ( lu <= l && r <= ru ) {
segTree[v].lazy = x;
propag( v, l, r );
return;
}
int mid = (l + r) / 2;
if ( segTree[v].leftSon == -1 )
segTree[v].leftSon = newNode();
updateInterval( segTree[v].leftSon, l, mid, lu, ru, x );
if ( segTree[v].leftSon == -1 )
segTree[v].leftSon = newNode();
updateInterval( segTree[v].rightSon, mid + 1, r, lu, ru, x );
segTree[v].maxx = max( segTree[segTree[v].leftSon].maxx, segTree[segTree[v].rightSon].maxx );
}
void updateInterval( int l, int r, long long x ) {
updateInterval( root, lst, rst, l, r, x );
}
long long query( int v, int l, int r, int lq, int rq ) {
propag( v, l, r );
if ( l > rq || r < lq )
return 0;
if ( lq <= l && r <= rq )
return segTree[v].maxx;
int mid = (l + r) / 2;
long long a = (segTree[v].leftSon == -1 ? 0 : query( segTree[v].leftSon, l, mid, lq, rq ) );
long long b = (segTree[v].rightSon == -1 ? 0 : query( segTree[v].rightSon, mid + 1, r, lq, rq ) );
return max( a, b );
}
long long query( int r ) {
return query( root, lst, rst, lst, r );
}
};
const int MAX_N = 2e5;
const int MAX_M = 2e5;
int n;
int h[MAX_N + 2], parent[MAX_N + 2], leftSon[MAX_N + 2], rightSon[MAX_N + 2];
star stars[MAX_M];
vector<int> starsByColumn[MAX_N + 2];
set<int> heights[MAX_N + 2];
SegTree ds[MAX_N + 2];
void calcCost( int v ) {
ds[v].init( 0, n + 1 );
if ( v == 0 )
return;
int l = leftSon[v], r = rightSon[v];
calcCost( leftSon[v] );
calcCost( rightSon[v] );
if ( heights[l].size() < heights[r].size())
swap( l, r );
vector<pair<int, long long>> upd;
heights[r].insert( h[v] );
for ( int x: heights[r] ) {
if ( x <= h[v] )
upd.push_back( { x, ds[l].query( x ) + ds[r].query( x ) } );
else
upd.push_back( { x, ds[l].query( h[v] ) + ds[r].query( x ) } );
}
swap( ds[v], ds[l] );
swap( heights[v], heights[l] );
for ( int x: heights[r] )
heights[v].insert( x );
ds[v].updateInterval( h[v] + 1, n + 1, ds[r].query( h[v] ));
for ( auto p: upd )
ds[v].updatePoint( p.first, p.second );
for ( int i: starsByColumn[v] ) {
ds[v].updatePoint( stars[i].j, ds[v].query( h[v] ) + stars[i].c );
heights[v].insert( stars[i].j );
}
heights[l].clear();
heights[r].clear();
ds[l].segTree.clear();
ds[r].segTree.clear();
}
signed main() {
int m;
long long total = 0;
cin >> n;
for ( int i = 1; i <= n; i++ )
cin >> h[i];
cin >> m;
for ( int i = 0; i < m; i++ ) {
cin >> stars[i].i >> stars[i].j >> stars[i].c;
total += stars[i].c;
}
h[n + 1] = n + 1;
vector<int> stack;
for ( int i = 1; i <= n + 1; i++ ) {
vector<int> path;
while ( !stack.empty() && h[i] >= h[stack.back()] ) {
path.push_back( stack.back() );
stack.pop_back();
}
path.push_back( i );
stack.push_back( i );
for ( int j = 0; j < path.size() - 1; j++ )
parent[path[j]] = path[j + 1];
}
for ( int v = 1; v <= n; v++ ) {
if ( v < parent[v] )
leftSon[parent[v]] = v;
else
rightSon[parent[v]] = v;
}
for ( int i = 0; i < m; i++ )
starsByColumn[stars[i].i].push_back( i );
calcCost( n + 1 );
cout << total - ds[n + 1].query( n );
return 0;
}
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct star {
int i, j, c;
};
struct SegTree {
struct node {
long long maxx, lazy;
int leftSon, rightSon;
};
int root, lst, rst;
vector<node> segTree;
int newNode() {
int v = segTree.size();
segTree.push_back( { 0, 0, -1, -1 } );
return v;
}
void init( int l, int r ) {
lst = l;
rst = r;
root = newNode();
}
void propag( int v, int l, int r ) {
segTree[v].maxx += segTree[v].lazy;
if ( l != r ) {
if ( segTree[v].leftSon == -1 )
segTree[v].leftSon = newNode();
segTree[segTree[v].leftSon].lazy += segTree[v].lazy;
if ( segTree[v].rightSon == -1 )
segTree[v].rightSon = newNode();
segTree[segTree[v].rightSon].lazy += segTree[v].lazy;
}
segTree[v].lazy = 0;
}
void updatePoint( int v, int l, int r, int p, long long x ) {
propag( v, l, r );
if ( l > p || r < p )
return;
if ( l == r ) {
segTree[v].maxx = max( segTree[v].maxx, x );
return;
}
int mid = (l + r) / 2;
if ( segTree[v].leftSon == -1 )
segTree[v].leftSon = newNode();
updatePoint( segTree[v].leftSon, l, mid, p, x );
if ( segTree[v].leftSon == -1 )
segTree[v].leftSon = newNode();
updatePoint( segTree[v].rightSon, mid + 1, r, p, x );
segTree[v].maxx = max( segTree[segTree[v].leftSon].maxx, segTree[segTree[v].rightSon].maxx );
}
void updatePoint( int p, long long x ) {
updatePoint( root, lst, rst, p, x );
}
void updateInterval( int v, int l, int r, int lu, int ru, long long x ) {
propag( v, l, r );
if ( l > ru || r < lu )
return;
if ( lu <= l && r <= ru ) {
segTree[v].lazy = x;
propag( v, l, r );
return;
}
int mid = (l + r) / 2;
if ( segTree[v].leftSon == -1 )
segTree[v].leftSon = newNode();
updateInterval( segTree[v].leftSon, l, mid, lu, ru, x );
if ( segTree[v].leftSon == -1 )
segTree[v].leftSon = newNode();
updateInterval( segTree[v].rightSon, mid + 1, r, lu, ru, x );
segTree[v].maxx = max( segTree[segTree[v].leftSon].maxx, segTree[segTree[v].rightSon].maxx );
}
void updateInterval( int l, int r, long long x ) {
updateInterval( root, lst, rst, l, r, x );
}
long long query( int v, int l, int r, int lq, int rq ) {
propag( v, l, r );
if ( l > rq || r < lq )
return 0;
if ( lq <= l && r <= rq )
return segTree[v].maxx;
int mid = (l + r) / 2;
long long a = (segTree[v].leftSon == -1 ? 0 : query( segTree[v].leftSon, l, mid, lq, rq ) );
long long b = (segTree[v].rightSon == -1 ? 0 : query( segTree[v].rightSon, mid + 1, r, lq, rq ) );
return max( a, b );
}
long long query( int r ) {
return query( root, lst, rst, lst, r );
}
};
const int MAX_N = 2e5;
const int MAX_M = 2e5;
int n;
int h[MAX_N + 2], parent[MAX_N + 2], leftSon[MAX_N + 2], rightSon[MAX_N + 2];
star stars[MAX_M];
vector<int> starsByColumn[MAX_N + 2];
set<int> heights[MAX_N + 2];
SegTree ds[MAX_N + 2];
void calcCost( int v ) {
ds[v].init( 0, n + 1 );
if ( v == 0 )
return;
int l = leftSon[v], r = rightSon[v];
calcCost( leftSon[v] );
calcCost( rightSon[v] );
if ( heights[l].size() < heights[r].size())
swap( l, r );
vector<pair<int, long long>> upd;
heights[r].insert( h[v] );
for ( int x: heights[r] ) {
if ( x <= h[v] )
upd.push_back( { x, ds[l].query( x ) + ds[r].query( x ) } );
else
upd.push_back( { x, ds[l].query( h[v] ) + ds[r].query( x ) } );
}
swap( ds[v], ds[l] );
swap( heights[v], heights[l] );
for ( int x: heights[r] )
heights[v].insert( x );
ds[v].updateInterval( h[v] + 1, n + 1, ds[r].query( h[v] ));
for ( auto p: upd )
ds[v].updatePoint( p.first, p.second );
for ( int i: starsByColumn[v] ) {
ds[v].updatePoint( stars[i].j, ds[v].query( h[v] ) + stars[i].c );
heights[v].insert( stars[i].j );
}
heights[l].clear();
heights[r].clear();
ds[l].segTree.clear();
ds[r].segTree.clear();
}
signed main() {
int m;
long long total = 0;
cin >> n;
for ( int i = 1; i <= n; i++ )
cin >> h[i];
cin >> m;
for ( int i = 0; i < m; i++ ) {
cin >> stars[i].i >> stars[i].j >> stars[i].c;
total += stars[i].c;
}
h[n + 1] = n + 1;
vector<int> stack;
for ( int i = 1; i <= n + 1; i++ ) {
vector<int> path;
while ( !stack.empty() && h[i] >= h[stack.back()] ) {
path.push_back( stack.back() );
stack.pop_back();
}
path.push_back( i );
stack.push_back( i );
for ( int j = 0; j < path.size() - 1; j++ )
parent[path[j]] = path[j + 1];
}
for ( int v = 1; v <= n; v++ ) {
if ( v < parent[v] )
leftSon[parent[v]] = v;
else
rightSon[parent[v]] = v;
}
for ( int i = 0; i < m; i++ )
starsByColumn[stars[i].i].push_back( i );
calcCost( n + 1 );
cout << total - ds[n + 1].query( n );
return 0;
}
Compilation message
constellation3.cpp: In function 'int main()':
constellation3.cpp:194:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
194 | for ( int j = 0; j < path.size() - 1; j++ )
| ~~^~~~~~~~~~~~~~~~~
constellation3.cpp: At global scope:
constellation3.cpp:220:8: error: redefinition of 'struct star'
220 | struct star {
| ^~~~
constellation3.cpp:7:8: note: previous definition of 'struct star'
7 | struct star {
| ^~~~
constellation3.cpp:224:8: error: redefinition of 'struct SegTree'
224 | struct SegTree {
| ^~~~~~~
constellation3.cpp:11:8: note: previous definition of 'struct SegTree'
11 | struct SegTree {
| ^~~~~~~
constellation3.cpp:330:11: error: redefinition of 'const long long int MAX_N'
330 | const int MAX_N = 2e5;
| ^~~~~
constellation3.cpp:117:11: note: 'const long long int MAX_N' previously defined here
117 | const int MAX_N = 2e5;
| ^~~~~
constellation3.cpp:331:11: error: redefinition of 'const long long int MAX_M'
331 | const int MAX_M = 2e5;
| ^~~~~
constellation3.cpp:118:11: note: 'const long long int MAX_M' previously defined here
118 | const int MAX_M = 2e5;
| ^~~~~
constellation3.cpp:332:5: error: redefinition of 'long long int n'
332 | int n;
| ^
constellation3.cpp:119:5: note: 'long long int n' previously declared here
119 | int n;
| ^
constellation3.cpp:333:5: error: redefinition of 'long long int h [200002]'
333 | int h[MAX_N + 2], parent[MAX_N + 2], leftSon[MAX_N + 2], rightSon[MAX_N + 2];
| ^
constellation3.cpp:120:5: note: 'long long int h [200002]' previously declared here
120 | int h[MAX_N + 2], parent[MAX_N + 2], leftSon[MAX_N + 2], rightSon[MAX_N + 2];
| ^
constellation3.cpp:333:19: error: redefinition of 'long long int parent [200002]'
333 | int h[MAX_N + 2], parent[MAX_N + 2], leftSon[MAX_N + 2], rightSon[MAX_N + 2];
| ^~~~~~
constellation3.cpp:120:19: note: 'long long int parent [200002]' previously declared here
120 | int h[MAX_N + 2], parent[MAX_N + 2], leftSon[MAX_N + 2], rightSon[MAX_N + 2];
| ^~~~~~
constellation3.cpp:333:38: error: redefinition of 'long long int leftSon [200002]'
333 | int h[MAX_N + 2], parent[MAX_N + 2], leftSon[MAX_N + 2], rightSon[MAX_N + 2];
| ^~~~~~~
constellation3.cpp:120:38: note: 'long long int leftSon [200002]' previously declared here
120 | int h[MAX_N + 2], parent[MAX_N + 2], leftSon[MAX_N + 2], rightSon[MAX_N + 2];
| ^~~~~~~
constellation3.cpp:333:58: error: redefinition of 'long long int rightSon [200002]'
333 | int h[MAX_N + 2], parent[MAX_N + 2], leftSon[MAX_N + 2], rightSon[MAX_N + 2];
| ^~~~~~~~
constellation3.cpp:120:58: note: 'long long int rightSon [200002]' previously declared here
120 | int h[MAX_N + 2], parent[MAX_N + 2], leftSon[MAX_N + 2], rightSon[MAX_N + 2];
| ^~~~~~~~
constellation3.cpp:334:6: error: redefinition of 'star stars [200000]'
334 | star stars[MAX_M];
| ^~~~~
constellation3.cpp:121:6: note: 'star stars [200000]' previously declared here
121 | star stars[MAX_M];
| ^~~~~
constellation3.cpp:335:13: error: redefinition of 'std::vector<long long int> starsByColumn [200002]'
335 | vector<int> starsByColumn[MAX_N + 2];
| ^~~~~~~~~~~~~
constellation3.cpp:122:13: note: 'std::vector<long long int> starsByColumn [200002]' previously declared here
122 | vector<int> starsByColumn[MAX_N + 2];
| ^~~~~~~~~~~~~
constellation3.cpp:336:10: error: redefinition of 'std::set<long long int> heights [200002]'
336 | set<int> heights[MAX_N + 2];
| ^~~~~~~
constellation3.cpp:123:10: note: 'std::set<long long int> heights [200002]' previously declared here
123 | set<int> heights[MAX_N + 2];
| ^~~~~~~
constellation3.cpp:337:9: error: redefinition of 'SegTree ds [200002]'
337 | SegTree ds[MAX_N + 2];
| ^~
constellation3.cpp:124:9: note: 'SegTree ds [200002]' previously declared here
124 | SegTree ds[MAX_N + 2];
| ^~
constellation3.cpp:339:6: error: redefinition of 'void calcCost(long long int)'
339 | void calcCost( int v ) {
| ^~~~~~~~
constellation3.cpp:126:6: note: 'void calcCost(long long int)' previously defined here
126 | void calcCost( int v ) {
| ^~~~~~~~
constellation3.cpp:383:8: error: redefinition of 'int main()'
383 | signed main() {
| ^~~~
constellation3.cpp:170:8: note: 'int main()' previously defined here
170 | signed main() {
| ^~~~
constellation3.cpp: In function 'int main()':
constellation3.cpp:407:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
407 | for ( int j = 0; j < path.size() - 1; j++ )
| ~~^~~~~~~~~~~~~~~~~
