Submission #1002768

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1002768	2024-06-19T19:30:27 Z	hyakup	Autobahn (COI21_autobahn)	C++17	Compilation error	0 ms	0 KB

autobahn

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define bug(x) cout << #x << " " << x << endl;

const ll inf = 1e9 + 10; 

int K; 

class sparse_seg{
    public:
        int create(){
            sum.push_back(0); 
            qtd.push_back(0); 
            tam.push_back(0); 
            l.push_back(0); 
            r.push_back(0); 
            lazy_qtd.push_back(0); 
            lazy_sum.push_back(0); 
            lazy_tam.push_back(0);
            return (int)sum.size() - 1; 
        }

        int left( int pos ){
            if( l[pos] == 0 ){ int aux = create(); l[pos] = aux; }
            return l[pos]; 
        }

        int right( int pos ){
            if( r[pos] == 0 ){ int aux = create(); r[pos] = aux; }
            return r[pos]; 
        }

        void refresh( int pos, int ini, int fim ){
            if( lazy_qtd[pos] == 0 && lazy_sum[pos] == 0 && lazy_tam[pos] == 0 ) return; 
            aux1 = lazy_qtd[pos]; lazy_qtd[pos] = 0; 
            aux2 = lazy_sum[pos]; lazy_sum[pos] = 0; 
            aux3 = lazy_tam[pos]; lazy_tam[pos] = 0; 
            qtd[pos] += aux1; 
            tam[pos] += (fim - ini + 1)*aux3; 
            sum[pos] += 1LL*tam[pos]*aux2; 
            if( ini == fim ) return; 
            left(pos); right(pos); 
            lazy_qtd[l[pos]] += aux1; 
            lazy_qtd[r[pos]] += aux1; 
            lazy_sum[l[pos]] += aux2; 
            lazy_sum[r[pos]] += aux2; 
            lazy_tam[l[pos]] += aux3; 
            lazy_tam[r[pos]] += aux3; 
        }

        void merge( int pos ){
            sum[pos] = sum[left(pos)] + sum[right(pos)]; 
            qtd[pos] = qtd[left(pos)] + qtd[right(pos)]; 
        }

        void update( int pos, int ini, int fim, int ki, int kf, int t ){
            refresh( pos, ini, fim ); 
            if( ki > fim || ini > kf ) return; 
            if( ki <= ini && fim <= kf ){
                if( t == 1 ) lazy_qtd[pos]++; 
                else lazy_sum[pos]++; 
                refresh(pos, ini, fim); 
                return; 
            }
            int mid = (ini + fim)/2; 
            update( left(pos), ini, mid, ki, kf, t); 
            update( right(pos), mid + 1, fim, ki, kf, t ); 
            merge( pos ); 
            // if( t == 2 ) cout << ini << " " << fim << endl;
            // if( t == 2 ) bug(sum[pos]);
        }

        void traverse( int pos, int ini, int fim ){
            refresh( pos, ini, fim ); 
            if( l[pos] == 0 && r[pos] == 0 ){
                if( qtd[pos] >= K ) lazy_tam[pos] = 1; 
                refresh( pos, ini, fim ); 
                return; 
            }
            int mid = (ini + fim)/2; 
            traverse( l[pos], ini, mid ); traverse( r[pos], mid + 1, fim ); 
            tam[pos] = tam[l[pos]] + tam[r[pos]];
            // cout << ini << " " << fim << endl;
            // bug(tam[pos]); 
        }

        ll query( int pos, int ini, int fim, int ki, int kf ){
            refresh( pos, ini, fim ); 
            if( ki > fim || ini > kf ) return 0; 
            if( ki <= ini && fim <= kf ){  return sum[pos];} 
            int mid = (ini + fim)/2; 
            return query( left(pos), ini, mid, ki, kf ) + query( right(pos), mid + 1, fim, ki, kf ); 
        }
        sparse_seg(){ create(); create(); }
    private:
        vector<ll> sum; 
        vector<int> qtd, tam, l, r, lazy_qtd, lazy_sum, lazy_tam; 
        int aux1, aux2, aux3; 
} seg; 

int main(){
    ios::sync_with_stdio(false); cin.tie(NULL);  
    int n, k, x; cin >> n >> k >> x; 
    K = k; 
    vector<int> l(n + 1), t(n + 1), r(n + 1); 
    for( int i = 1; i <= n; i++ ){
        cin >> l[i] >> t[i] >> r[i]; 
        // bug(i); 
        seg.update( 1, 1, inf, l[i], r[i], 1 ); 
    }
    seg.traverse( 1, 1, inf ); 
    for( int i = 1; i <= n; i++ ){
        // bug(i); 
        // bug(l[i] + t[i]); 
        // bug(r[i]); 
        if( l[i] + t[i] <= r[i] ) seg.update( 1, 1, inf, l[i] + t[i], r[i], 2 ); 
    }

    ll resp = 0; 
    for( int i = 1; i <= n; i++ ){
        resp = max( resp, seg.query( 1, 1, inf, l[i] + t[i], min( l[i] + t[i] + x - 1, inf ) ) ); 
        resp = max( resp, seg.query( 1, 1, inf, max( 1LL, r[i] - x + 1), r[i] ) ); 
    }
    cout << resp << endl;
}

Compilation message

autobahn.cpp: In function 'int main()':
autobahn.cpp:122:92: error: no matching function for call to 'min(__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type, const long long int&)'
  122 |         resp = max( resp, seg.query( 1, 1, inf, l[i] + t[i], min( l[i] + t[i] + x - 1, inf ) ) );
      |                                                                                            ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from autobahn.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:230:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  230 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:230:5: note:   template argument deduction/substitution failed:
autobahn.cpp:122:92: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
  122 |         resp = max( resp, seg.query( 1, 1, inf, l[i] + t[i], min( l[i] + t[i] + x - 1, inf ) ) );
      |                                                                                            ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from autobahn.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:278:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  278 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:278:5: note:   template argument deduction/substitution failed:
autobahn.cpp:122:92: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
  122 |         resp = max( resp, seg.query( 1, 1, inf, l[i] + t[i], min( l[i] + t[i] + x - 1, inf ) ) );
      |                                                                                            ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from autobahn.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3468:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)'
 3468 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3468:5: note:   template argument deduction/substitution failed:
autobahn.cpp:122:92: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  122 |         resp = max( resp, seg.query( 1, 1, inf, l[i] + t[i], min( l[i] + t[i] + x - 1, inf ) ) );
      |                                                                                            ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from autobahn.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3474:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)'
 3474 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3474:5: note:   template argument deduction/substitution failed:
autobahn.cpp:122:92: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  122 |         resp = max( resp, seg.query( 1, 1, inf, l[i] + t[i], min( l[i] + t[i] + x - 1, inf ) ) );
      |                                                                                            ^
autobahn.cpp:123:71: error: no matching function for call to 'max(long long int, __gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type)'
  123 |         resp = max( resp, seg.query( 1, 1, inf, max( 1LL, r[i] - x + 1), r[i] ) );
      |                                                                       ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from autobahn.cpp:1:
/usr/include/c++/10/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++/10/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
autobahn.cpp:123:71: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'})
  123 |         resp = max( resp, seg.query( 1, 1, inf, max( 1LL, r[i] - x + 1), r[i] ) );
      |                                                                       ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from autobahn.cpp:1:
/usr/include/c++/10/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++/10/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
autobahn.cpp:123:71: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'})
  123 |         resp = max( resp, seg.query( 1, 1, inf, max( 1LL, r[i] - x + 1), r[i] ) );
      |                                                                       ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from autobahn.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3480 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note:   template argument deduction/substitution failed:
autobahn.cpp:123:71: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  123 |         resp = max( resp, seg.query( 1, 1, inf, max( 1LL, r[i] - x + 1), r[i] ) );
      |                                                                       ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from autobahn.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3486 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note:   template argument deduction/substitution failed:
autobahn.cpp:123:71: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  123 |         resp = max( resp, seg.query( 1, 1, inf, max( 1LL, r[i] - x + 1), r[i] ) );
      |                                                                       ^