#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;
segTree[v].maxx = max( segTree[v].maxx, x );
if ( l == r )
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 );
}
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;
segTree[v].maxx = max( segTree[v].maxx, x );
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];
long long dp[2002][2002];
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[v] )
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 );
}
for ( int x = 0; x <= n; x++ ) {
if ( x <= h[v] )
dp[v][x] = dp[leftSon[v]][x] + dp[rightSon[v]][x];
else
dp[v][x] = max( dp[leftSon[v]][x] + dp[rightSon[v]][h[v]], dp[leftSon[v]][h[v]] + dp[rightSon[v]][x] );
}
for ( int i: starsByColumn[v] )
dp[v][stars[i].j] = max( dp[v][stars[i].j], dp[v][h[v]] + stars[i].c );
for ( int x = 1; x <= n; x++ )
dp[v][x] = max( dp[v][x], dp[v][x - 1] );
}
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:199: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]
199 | for ( int j = 0; j < path.size() - 1; j++ )
| ~~^~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
9 ms |
38488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
9 ms |
38488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
9 ms |
38488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
