Submission #811639

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
811639	2023-08-07T05:12:18 Z	vjudge1	Financial Report (JOI21_financial)	C++14	Compilation error	0 ms	0 KB

Main

#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
using namespace std ;
const int N = (1 << 19) ;
int n, d, cnt, a[N + 1], dp[N + 1], mx[2 * N + 1] ;
set<int> s ;
map<int, int> mp ;
void update(int l, int r, int ind, int num, int v)
{
    if(l > ind || r < ind)
        return ;
    if(l == r)
    {
        mx[v] = num ;
        return ;
    }
    int mid = (l + r) >> 1 ;
    update(l, mid, ind, num, v * 2) ;
    update(mid + 1, r, ind, num, v * 2 + 1) ;
    mx[v] = max(mx[v * 2], mx[v * 2 + 1]) ;
}
int get_max(int l, int r,int l1, int r1, int v)
{
    if(l > r1 || r < l1)
        return 0 ;
    if(l1 <= l && r <= r1)
        return mx[v] ;
    int mid = (l + r) >> 1 ;
    return max(get_max(l, mid, l1, r1, v * 2), get_max(mid + 1, r, l1, r1, v * 2 + 1)) ;
}
signed main()
{
    ios_base::sync_with_stdio( 0 ) ;
    cin.tie( 0 ) ;
    cout.tie( 0 ) ;
    cin >> n >> d ;
    for(int i = 1 ; i <= n ; i++)
    {
        cin >> a[i] ;
        s.insert(a[i]) ;
    }
    for(int i : s)
    {
        cnt++ ;
        mp[i] = cnt ;
    }
    for(int i = 1 ; i <= n ; i++)
        a[i] = mp[a[i]] ;
    if(n <= 7000)
    {
        int ans = 0 ;
        for(int i = n ; i >= 1 ; i--)
        {
            int mx = 0, ls = i, now = a[i] ;
            pair<int, int> mn = {1e9, 1e9} ;
            for(int j = i + 1 ; j <= n ; j++)
            {
                mn = min(mn, {a[j], j}) ;
                if(a[j] > now)
                    mx = max(mx, dp[j]) ;
                if((j - ls) == d)
                {
                    ls = mn.se ;
                    now = max(now, mn.fi) ;
                    mn = 1e9 ;
                }
            }
            dp[i] = mx + 1 ;
            ans = max(ans, dp[i]) ;
        }
        cout << ans ;
        return 0 ;
    }
    if(n <= 20)
    {
        int ans = 0 ;
        for(int i = 0 ; i < (1 << n) ; i++)
        {
            int now = 0, mx = -1, ls = 1e9 ;
            for(int j = 0 ; j < n ; j++)
                if(j - ls <= d && ((1 << j) & i))
                {
                    ls = j ;
                    if(mx < a[j + 1])
                        now++ ;
                    mx = max(mx, a[j + 1]) ;
                }
            ans = max(ans, now) ;
        }
        cout << ans ;
        return 0 ;
    }
    if(d == 1)
    {
        int ans = 0 ;
        for(int i = 1 ; i <= n ; i++)
            update(1, N, i, a[i], 1) ;
        for(int i = n ; i >= 1 ; i--)
        {
            int l = i, r = n + 1 ;
            while(l + 1 < r)
            {
                int mid = (l + r) >> 1 ;
                if(get_max(1, N, i, mid, 1) > a[i])
                    r = mid ;
                else
                    l = mid ;
            }
            dp[i] = dp[r] + 1 ;
            ans = max(ans, dp[i]) ;
        }
        cout << ans ;
        return 0 ;
    }
    if(d == n)
    {
        int ans = 0 ;
        for(int i = 1 ; i <= n ; i++)
        {
            int num = get_max(1, N, 1, a[i] - 1, 1) ;
            ans = max(ans, num + 1) ;
            update(1, N, a[i], num + 1, 1) ;
        }
        cout << ans ;
        return 0 ;
    }
    return 0 ;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:67:26: error: no match for 'operator=' (operand types are 'std::pair<int, int>' and 'double')
   67 |                     mn = 1e9 ;
      |                          ^~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from Main.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:390:7: note: candidate: 'std::pair<_T1, _T2>& std::pair<_T1, _T2>::operator=(typename std::conditional<std::__and_<std::is_copy_assignable<_T1>, std::is_copy_assignable<_T2> >::value, const std::pair<_T1, _T2>&, const std::__nonesuch&>::type) [with _T1 = int; _T2 = int; typename std::conditional<std::__and_<std::is_copy_assignable<_T1>, std::is_copy_assignable<_T2> >::value, const std::pair<_T1, _T2>&, const std::__nonesuch&>::type = const std::pair<int, int>&]'
  390 |       operator=(typename conditional<
      |       ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:393:41: note:   no known conversion for argument 1 from 'double' to 'std::conditional<true, const std::pair<int, int>&, const std::__nonesuch&>::type' {aka 'const std::pair<int, int>&'}
  390 |       operator=(typename conditional<
      |                 ~~~~~~~~~~~~~~~~~~~~~    
  391 |   __and_<is_copy_assignable<_T1>,
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~        
  392 |          is_copy_assignable<_T2>>::value,
      |          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  393 |   const pair&, const __nonesuch&>::type __p)
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_pair.h:401:7: note: candidate: 'std::pair<_T1, _T2>& std::pair<_T1, _T2>::operator=(typename std::conditional<std::__and_<std::is_move_assignable<_Tp>, std::is_move_assignable<_T2> >::value, std::pair<_T1, _T2>&&, std::__nonesuch&&>::type) [with _T1 = int; _T2 = int; typename std::conditional<std::__and_<std::is_move_assignable<_Tp>, std::is_move_assignable<_T2> >::value, std::pair<_T1, _T2>&&, std::__nonesuch&&>::type = std::pair<int, int>&&]'
  401 |       operator=(typename conditional<
      |       ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:404:31: note:   no known conversion for argument 1 from 'double' to 'std::conditional<true, std::pair<int, int>&&, std::__nonesuch&&>::type' {aka 'std::pair<int, int>&&'}
  401 |       operator=(typename conditional<
      |                 ~~~~~~~~~~~~~~~~~~~~~
  402 |   __and_<is_move_assignable<_T1>,
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  403 |          is_move_assignable<_T2>>::value,
      |          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  404 |   pair&&, __nonesuch&&>::type __p)
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_pair.h:418:2: note: candidate: 'template<class _U1, class _U2> typename std::enable_if<std::__and_<std::is_assignable<_T1&, const _U1&>, std::is_assignable<_T2&, const _U2&> >::value, std::pair<_T1, _T2>&>::type std::pair<_T1, _T2>::operator=(const std::pair<_U1, _U2>&) [with _U1 = _U1; _U2 = _U2; _T1 = int; _T2 = int]'
  418 |  operator=(const pair<_U1, _U2>& __p)
      |  ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:418:2: note:   template argument deduction/substitution failed:
Main.cpp:67:26: note:   mismatched types 'const std::pair<_T1, _T2>' and 'double'
   67 |                     mn = 1e9 ;
      |                          ^~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from Main.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:430:2: note: candidate: 'template<class _U1, class _U2> typename std::enable_if<std::__and_<std::is_assignable<_T1&, _U1&&>, std::is_assignable<_T2&, _U2&&> >::value, std::pair<_T1, _T2>&>::type std::pair<_T1, _T2>::operator=(std::pair<_U1, _U2>&&) [with _U1 = _U1; _U2 = _U2; _T1 = int; _T2 = int]'
  430 |  operator=(pair<_U1, _U2>&& __p)
      |  ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:430:2: note:   template argument deduction/substitution failed:
Main.cpp:67:26: note:   mismatched types 'std::pair<_T1, _T2>' and 'double'
   67 |                     mn = 1e9 ;
      |                          ^~~