Submission #779676

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
779676	2023-07-11T16:05:34 Z	Ahmed57	Abduction 2 (JOI17_abduction2)	C++17	Compilation error	0 ms	0 KB

abduction2

#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")

#include <bits/stdc++.h>
using namespace std;
//dir = 0 left
//dir = 1 right
//dir = 2 up
//dir = 3 down
unordered_map<int,long long>dp[50001][4];
int n,m,q;int logg[50001];
int arr1[50001],arr2[50001];
int spar1[50001][16];
int spar2[50001][16];
int query1(int l,int r){
    int sz = r-l+1;
    return max(spar1[l][logg[sz]],spar1[r-(1<<logg[sz])+1][logg[sz]]);
}
int query2(int l,int r){
    int sz = r-l+1;
    return max(spar2[l][logg[sz]],spar2[r-(1<<logg[sz])+1][logg[sz]]);
}
long long solve(int x,int y,int dir){
    if(x<0||x>=n||y<0||y>=m)return -1;
    //cout<<x<<" "<<y<<" "<<dir<<endl;
    if(dp[x][dir].count(y)!=0)return dp[x][dir][y];
    //cout<<x<<" "<<y<<" "<<dir<<endl;
    if(dir==0){
        int l = 0, r = y , ans = -1;
        while(l<=r){
            int mid = (l+r)/2;
            if(query2(mid,y)>arr1[x]){
                ans = mid;
                l = mid+1;
            }else r = mid-1;
        }
        //cout<<y<<" "<<ans<<" "<<dir<<endl;
        if(ans!=-1){
            long long c1 = 0;
            c1 = max(c1,solve(x-1,ans,2)+1);
            c1 = max(c1,solve(x+1,ans,3)+1);
            return dp[x][dir][y] = c1+(y-ans);
        }else{
            return dp[x][dir][y] = y;
        }
    }if(dir==1){
        int l = y, r = m-1 , ans = -1;
        while(l<=r){
            int mid = (l+r)/2;
            if(query2(y,mid)>arr1[x]){
                ans = mid;
                r = mid-1;
            }else l = mid+1;
        }
        //cout<<y<<" "<<ans<<" "<<dir<<endl;
        if(ans!=-1){
            long long c1 = 0;
            c1 = max(c1,solve(x-1,ans,2)+1);
            c1 = max(c1,solve(x+1,ans,3)+1);
            return dp[x][dir][y] = c1+(ans-y);
        }else{
            return dp[x][dir][y] = (m-1)-y;
        }
    }if(dir==2){
        int l = 0, r = x , ans = -1;
        while(l<=r){
            int mid = (l+r)/2;
            if(query1(mid,x)>arr2[y]){
                ans = mid;
                l = mid+1;
            }else r = mid-1;
        }
        //cout<<x<<" "<<ans<<" "<<dir<<endl;
        if(ans!=-1){
            long long c1 = 0;
            c1 = max(c1,solve(ans,y-1,0)+1);
            c1 = max(c1,solve(ans,y+1,1)+1);
            return dp[x][dir][y] = c1+(x-ans);
        }else{
            return dp[x][dir][y] = x;
        }
    }if(dir==3){
        int l = x, r = n-1 , ans = -1;
        while(l<=r){
            int mid = (l+r)/2;
            if(query1(x,mid)>arr2[y]){
                ans = mid;
                r = mid-1;
            }else l = mid+1;
        }
        //cout<<x<<" "<<ans<<" "<<dir<<endl;
        if(ans!=-1){
            long long c1 = 0;
            c1 = max(c1,solve(ans,y-1,0)+1);
            c1 = max(c1,solve(ans,y+1,1)+1);
            return dp[x][dir][y] = c1+(ans-x);
        }else{
            return dp[x][dir][y] = (n-1)-x;
        }
    }
}
int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>m>>q;
    for(int i = 0;i<n;i++)cin>>arr1[i];
    for(int i = 0;i<m;i++)cin>>arr2[i];
    for(int i = 0;i<n;i++)spar1[i][0] = arr1[i];
    for(int i = 0;i<m;i++)spar2[i][0] = arr2[i];
    for(int j = 1;j<16;j++){
        for(int i = 0;i<n;i++){
            if(i+(1<<j)>n)break;
            spar1[i][j] = max(spar1[i][j-1],spar1[i+(1<<(j-1))][j-1]);
        }
    }
    for(int j = 1;j<16;j++){
        for(int i = 0;i<m;i++){
            if(i+(1<<j)>m)break;
            spar2[i][j] = max(spar2[i][j-1],spar2[i+(1<<(j-1))][j-1]);
        }
    }
    logg[1] = 0;
    for(int i = 2;i<=50000;i++)logg[i] = logg[i/2]+1;
    while(q--){
        int a,b;cin>>a>>b;
        a--;b--;
        int ans = 0;
        ans = max(ans,solve(a,b-1,0)+1);
        ans = max(ans,solve(a,b+1,1)+1);
        ans = max(ans,solve(a-1,b,2)+1);
        ans = max(ans,solve(a+1,b,3)+1);
        cout<<ans<<"\n";
    }
}

Compilation message

abduction2.cpp: In function 'int main()':
abduction2.cpp:126:39: error: no matching function for call to 'max(int&, long long int)'
  126 |         ans = max(ans,solve(a,b-1,0)+1);
      |                                       ^
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 abduction2.cpp:3:
/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:
abduction2.cpp:126:39: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
  126 |         ans = max(ans,solve(a,b-1,0)+1);
      |                                       ^
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 abduction2.cpp:3:
/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:
abduction2.cpp:126:39: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
  126 |         ans = max(ans,solve(a,b-1,0)+1);
      |                                       ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from abduction2.cpp:3:
/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:
abduction2.cpp:126:39: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  126 |         ans = max(ans,solve(a,b-1,0)+1);
      |                                       ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from abduction2.cpp:3:
/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:
abduction2.cpp:126:39: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  126 |         ans = max(ans,solve(a,b-1,0)+1);
      |                                       ^
abduction2.cpp:127:39: error: no matching function for call to 'max(int&, long long int)'
  127 |         ans = max(ans,solve(a,b+1,1)+1);
      |                                       ^
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 abduction2.cpp:3:
/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:
abduction2.cpp:127:39: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
  127 |         ans = max(ans,solve(a,b+1,1)+1);
      |                                       ^
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 abduction2.cpp:3:
/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:
abduction2.cpp:127:39: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
  127 |         ans = max(ans,solve(a,b+1,1)+1);
      |                                       ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from abduction2.cpp:3:
/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:
abduction2.cpp:127:39: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  127 |         ans = max(ans,solve(a,b+1,1)+1);
      |                                       ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from abduction2.cpp:3:
/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:
abduction2.cpp:127:39: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  127 |         ans = max(ans,solve(a,b+1,1)+1);
      |                                       ^
abduction2.cpp:128:39: error: no matching function for call to 'max(int&, long long int)'
  128 |         ans = max(ans,solve(a-1,b,2)+1);
      |                                       ^
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 abduction2.cpp:3:
/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:
abduction2.cpp:128:39: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
  128 |         ans = max(ans,solve(a-1,b,2)+1);
      |                                       ^
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 abduction2.cpp:3:
/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:
abduction2.cpp:128:39: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
  128 |         ans = max(ans,solve(a-1,b,2)+1);
      |                                       ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from abduction2.cpp:3:
/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:
abduction2.cpp:128:39: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  128 |         ans = max(ans,solve(a-1,b,2)+1);
      |                                       ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from abduction2.cpp:3:
/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:
abduction2.cpp:128:39: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  128 |         ans = max(ans,solve(a-1,b,2)+1);
      |                                       ^
abduction2.cpp:129:39: error: no matching function for call to 'max(int&, long long int)'
  129 |         ans = max(ans,solve(a+1,b,3)+1);
      |                                       ^
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 abduction2.cpp:3:
/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:
abduction2.cpp:129:39: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
  129 |         ans = max(ans,solve(a+1,b,3)+1);
      |                                       ^
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 abduction2.cpp:3:
/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:
abduction2.cpp:129:39: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
  129 |         ans = max(ans,solve(a+1,b,3)+1);
      |                                       ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from abduction2.cpp:3:
/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:
abduction2.cpp:129:39: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  129 |         ans = max(ans,solve(a+1,b,3)+1);
      |                                       ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from abduction2.cpp:3:
/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:
abduction2.cpp:129:39: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  129 |         ans = max(ans,solve(a+1,b,3)+1);
      |                                       ^
abduction2.cpp: In function 'long long int solve(int, int, int)':
abduction2.cpp:100:1: warning: control reaches end of non-void function [-Wreturn-type]
  100 | }
      | ^