Submission #1123561

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123561		LucaIlie	Fire (JOI20_ho_t5)	C++20	Compilation error	0 ms	0 KiB

ho_t5

#include <bits/stdc++.h>

#define int long long

using namespace std;

struct query {
    int t, l, r;
    long long ans;
};

const int MAX_N = 2e5;
const int MAX_Q = 2e5;
int a[MAX_N + 1], leftt[MAX_N + 1], rightt[MAX_N + 1], timeIncrease[MAX_N + 1];
vector<int> queriesByTime[MAX_N + 1];
vector<int> increasingSegmentsByTime[MAX_N + 1], constantSegmentsByTime[MAX_N + 1];
query queries[MAX_Q];

void computeSegmentEvents( int n, int sign ) {
    set<int> increasingSegments, constantSegments;
    for ( int t = 0; t <= n; t++ ) {
        for ( int i: increasingSegmentsByTime[t] ) {
            if ( increasingSegments.find( i ) == increasingSegments.end() )
                increasingSegments.insert( i );
            else
                increasingSegments.erase( i );
        }
        for ( int i: constantSegmentsByTime[t] ) {
            if ( constantSegments.find( i ) == constantSegments.end() )
                constantSegments.insert( i );
            else
                constantSegments.erase( i );
        }

        for ( int i: queriesByTime[t] ) {
            //printf( "QUERY %d\n", i );
            for ( int j: increasingSegments )
                queries[i].ans += sign * a[j] * max( 0, min( j + t - timeIncrease[j], queries[i].r ) - max( j, queries[i].l ) + 1 );//, printf( "increas %d %d\n", j, j + t - timeIncrease[j] );
            for ( int j: constantSegments )
                queries[i].ans += sign * a[j] * max( 0, min( rightt[j] - 1, queries[i].r ) - max( j, queries[i].l ) + 1 );//, printf( "cst %d %d\n", j, rightt[j - 1] - 1 );
            //printf( "\n\n\n" );
        }
    }
}

signed main() {
    int n, q;

    cin >> n >> q;
    for ( int i = 1; i <= n; i++ )
        cin >> a[i];
    for ( int i = 0; i < q; i++ ) {
        cin >> queries[i].t >> queries[i].l >> queries[i].r;
        queriesByTime[queries[i].t].push_back( i );
    }

    vector<int> stack;
    for ( int i = 1; i <= n; i++ ) {
        while ( !stack.empty() && a[i] > a[stack.back()] )
            stack.pop_back();
        if ( !stack.empty() )
            leftt[i] = stack.back();
        else
            leftt[i] = -(n + 1);
        stack.push_back( i );
    }
    while ( !stack.empty() )
        stack.pop_back();
    for ( int i = n; i >= 1; i-- ) {
        while ( !stack.empty() && a[i] > a[stack.back()] )
            stack.pop_back();
        if ( !stack.empty() )
            rightt[i] = stack.back();
        else
            rightt[i] = (n + 1);
        stack.push_back( i );
    }

    for ( int t = 0; t <= n; t++ ) {
        increasingSegmentsByTime[t].clear();
        constantSegmentsByTime[t].clear();
    }
    for ( int i = 1; i <= n; i++ ) { // update + on trapezoid
        int goDown = i - leftt[i], goIncreasing = rightt[i] - i;
        timeIncrease[i] = 0;
        increasingSegmentsByTime[0].push_back( i );
        increasingSegmentsByTime[goIncreasing].push_back( i );
        constantSegmentsByTime[goIncreasing].push_back( i );
        constantSegmentsByTime[goIncreasing + goDown - 1].push_back( i );
    }
    computeSegmentEvents( n, 1 );

    for ( int t = 0; t <= n; t++ ) {
        increasingSegmentsByTime[t].clear();
        constantSegmentsByTime[t].clear();
    }
    for ( int i = 1; i <= n; i++ ) { // update - on triangle
        int goDown = i - leftt[i], goIncreasing = rightt[i] - i;
        timeIncrease[i] = goDown;
        increasingSegmentsByTime[goDown].push_back( i );
        increasingSegmentsByTime[goDown + goIncreasing - 1].push_back( i );
    }
    computeSegmentEvents( n, -1 );

    for ( int i = 0; i < q; i++ )
        cout << queries[i].ans << "\n";

    return 0;
}

Compilation message (stderr)

ho_t5.cpp: In function 'void computeSegmentEvents(long long int, long long int)':
ho_t5.cpp:38:52: error: no matching function for call to 'max(int, long long int)'
   38 |                 queries[i].ans += sign * a[j] * max( 0, min( j + t - timeIncrease[j], queries[i].r ) - max( j, queries[i].l ) + 1 );//, printf( "increas %d %d\n", j, j + t - timeIncrease[j] );
      |                                                 ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/bits/specfun.h:45,
                 from /usr/include/c++/11/cmath:1935,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from ho_t5.cpp:1:
/usr/include/c++/11/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/11/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
ho_t5.cpp:38:52: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
   38 |                 queries[i].ans += sign * a[j] * max( 0, min( j + t - timeIncrease[j], queries[i].r ) - max( j, queries[i].l ) + 1 );//, printf( "increas %d %d\n", j, j + t - timeIncrease[j] );
      |                                                 ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/bits/specfun.h:45,
                 from /usr/include/c++/11/cmath:1935,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from ho_t5.cpp:1:
/usr/include/c++/11/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/11/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
ho_t5.cpp:38:52: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
   38 |                 queries[i].ans += sign * a[j] * max( 0, min( j + t - timeIncrease[j], queries[i].r ) - max( j, queries[i].l ) + 1 );//, printf( "increas %d %d\n", j, j + t - timeIncrease[j] );
      |                                                 ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/string:52,
                 from /usr/include/c++/11/bits/locale_classes.h:40,
                 from /usr/include/c++/11/bits/ios_base.h:41,
                 from /usr/include/c++/11/ios:42,
                 from /usr/include/c++/11/istream:38,
                 from /usr/include/c++/11/sstream:38,
                 from /usr/include/c++/11/complex:45,
                 from /usr/include/c++/11/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
                 from ho_t5.cpp:1:
/usr/include/c++/11/bits/stl_algo.h:3461:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3461 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/11/bits/stl_algo.h:3461:5: note:   template argument deduction/substitution failed:
ho_t5.cpp:38:52: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   38 |                 queries[i].ans += sign * a[j] * max( 0, min( j + t - timeIncrease[j], queries[i].r ) - max( j, queries[i].l ) + 1 );//, printf( "increas %d %d\n", j, j + t - timeIncrease[j] );
      |                                                 ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/string:52,
                 from /usr/include/c++/11/bits/locale_classes.h:40,
                 from /usr/include/c++/11/bits/ios_base.h:41,
                 from /usr/include/c++/11/ios:42,
                 from /usr/include/c++/11/istream:38,
                 from /usr/include/c++/11/sstream:38,
                 from /usr/include/c++/11/complex:45,
                 from /usr/include/c++/11/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
                 from ho_t5.cpp:1:
/usr/include/c++/11/bits/stl_algo.h:3467:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3467 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/11/bits/stl_algo.h:3467:5: note:   template argument deduction/substitution failed:
ho_t5.cpp:38:52: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   38 |                 queries[i].ans += sign * a[j] * max( 0, min( j + t - timeIncrease[j], queries[i].r ) - max( j, queries[i].l ) + 1 );//, printf( "increas %d %d\n", j, j + t - timeIncrease[j] );
      |                                                 ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ho_t5.cpp:40:52: error: no matching function for call to 'max(int, long long int)'
   40 |                 queries[i].ans += sign * a[j] * max( 0, min( rightt[j] - 1, queries[i].r ) - max( j, queries[i].l ) + 1 );//, printf( "cst %d %d\n", j, rightt[j - 1] - 1 );
      |                                                 ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/bits/specfun.h:45,
                 from /usr/include/c++/11/cmath:1935,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from ho_t5.cpp:1:
/usr/include/c++/11/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/11/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
ho_t5.cpp:40:52: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
   40 |                 queries[i].ans += sign * a[j] * max( 0, min( rightt[j] - 1, queries[i].r ) - max( j, queries[i].l ) + 1 );//, printf( "cst %d %d\n", j, rightt[j - 1] - 1 );
      |                                                 ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/bits/specfun.h:45,
                 from /usr/include/c++/11/cmath:1935,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from ho_t5.cpp:1:
/usr/include/c++/11/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/11/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
ho_t5.cpp:40:52: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
   40 |                 queries[i].ans += sign * a[j] * max( 0, min( rightt[j] - 1, queries[i].r ) - max( j, queries[i].l ) + 1 );//, printf( "cst %d %d\n", j, rightt[j - 1] - 1 );
      |                                                 ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/string:52,
                 from /usr/include/c++/11/bits/locale_classes.h:40,
                 from /usr/include/c++/11/bits/ios_base.h:41,
                 from /usr/include/c++/11/ios:42,
                 from /usr/include/c++/11/istream:38,
                 from /usr/include/c++/11/sstream:38,
                 from /usr/include/c++/11/complex:45,
                 from /usr/include/c++/11/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
                 from ho_t5.cpp:1:
/usr/include/c++/11/bits/stl_algo.h:3461:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3461 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/11/bits/stl_algo.h:3461:5: note:   template argument deduction/substitution failed:
ho_t5.cpp:40:52: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   40 |                 queries[i].ans += sign * a[j] * max( 0, min( rightt[j] - 1, queries[i].r ) - max( j, queries[i].l ) + 1 );//, printf( "cst %d %d\n", j, rightt[j - 1] - 1 );
      |                                                 ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/string:52,
                 from /usr/include/c++/11/bits/locale_classes.h:40,
                 from /usr/include/c++/11/bits/ios_base.h:41,
                 from /usr/include/c++/11/ios:42,
                 from /usr/include/c++/11/istream:38,
                 from /usr/include/c++/11/sstream:38,
                 from /usr/include/c++/11/complex:45,
                 from /usr/include/c++/11/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
                 from ho_t5.cpp:1:
/usr/include/c++/11/bits/stl_algo.h:3467:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3467 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/11/bits/stl_algo.h:3467:5: note:   template argument deduction/substitution failed:
ho_t5.cpp:40:52: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   40 |                 queries[i].ans += sign * a[j] * max( 0, min( rightt[j] - 1, queries[i].r ) - max( j, queries[i].l ) + 1 );//, printf( "cst %d %d\n", j, rightt[j - 1] - 1 );
      |                                                 ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~