Submission #959967

#	Time	Username	Problem	Language	Result	Execution time	Memory
959967		LucaIlie	Constellation 3 (JOI20_constellation3)	C++17	Compilation error	0 ms	0 KiB

constellation3

#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 (stderr)

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++ )
      |                          ~~^~~~~~~~~~~~~~~~~