Submission #551938

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
551938	2022-04-21T23:05:16 Z	Lobo	Abduction 2 (JOI17_abduction2)	C++17	Compilation error	0 ms	0 KB

abduction2

#include<bits/stdc++.h>
using namespace std;

const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
// #define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

const int maxn = 5e4+10;

int n, m, q, a[maxn], b[maxn];
map<int,int> mark[maxn][5], dp[maxn][5];
pair<int,int> mxalf[maxn][25], mxarg[maxn][25], mxblf[maxn][25], mxbrg[maxn][25];

//ver com 32 tambem
int mxblr(int l, int r) {
    if(l > r) return -1;
    int lg = 31-__builtin_clz(r-l+1);
    auto ans = max(mxbrg[l][lg],mxblf[r][lg]);
    return ans.fr;
}
int mxalr(int l, int r) {
    if(l > r) return -1;
    int lg = 31-__builtin_clz(r-l+1);
    auto ans = max(mxarg[l][lg],mxalf[r][lg]);
    return ans.fr;
}
    
//0 -> x aumenta, 1 -> x diminui e dobra para vertical
//2 -> y aumenta, 3 -> y diminui
//x -> M e y-> N
int cnt = 0;
int sol(int y, int x, int dir) {
    if(mark[y][dir][x]) return dp[y][dir][x];
    mark[y][dir][x] = 1;


    if(dir == 0) {
        //vou para um (x1,y) que b[x1] > a[y] e x1 > x
        if(mxblr(x+1,m) < a[y]) {
            return dp[y][dir][x] = m-x;
        }

        int l = x+1;
        int r = m;
        int ans = -1;

        while(l <= r) {
            int mid = (l+r)/2;

            if(mxblr(x+1,mid) >= a[y]) {
                ans = mid;
                r = mid-1;
            }
            else {
                l = mid+1;
            }
        }

        return dp[y][dir][x] = ans-x+max(sol(y,ans,2),sol(y,ans,3));
    }
    else if(dir == 1) {
        //vou para um (x1,y) que b[x1] > a[y] e x1 < x
        if(mxblr(1,x-1) < a[y]) {
            return dp[y][dir][x] = x-1;
        }

        int l = 1;
        int r = x-1;
        int ans = -1;

        while(l <= r) {
            int mid = (l+r)/2;

            if(mxblr(mid,x-1) >= a[y]) {
                ans = mid;
                l = mid+1;
            }
            else {
                r = mid-1;
            }
        }

        return dp[y][dir][x] = x-ans+max(sol(y,ans,2),sol(y,ans,3));
    }
    else if(dir == 2) {
        //vou para um (x,y1) que a[y1] > b[x] e y1 > y
        if(mxalr(y+1,n) < b[x]) {
            return dp[y][dir][x] = n-y;
        }

        int l = y+1;
        int r = n;
        int ans = -1;

        while(l <= r) {
            int mid = (l+r)/2;

            if(mxalr(y+1,mid) >= b[x]) {
                ans = mid;
                r = mid-1;
            }
            else {
                l = mid+1;
            }
        }

        return dp[y][dir][x] = ans-y+max(sol(ans,x,0),sol(ans,x,1));
    }
    else {
        //vou para um (x,y1) que a[y1] > b[x] e y1 < y
        if(mxalr(1,y-1) < b[x]) {
            return dp[y][dir][x] = y-1;
        }

        int l = 1;
        int r = y-1;
        int ans = -1;

        while(l <= r) {
            int mid = (l+r)/2;

            if(mxalr(mid,y-1) >= b[x]) {
                ans = mid;
                l = mid+1;
            }
            else {
                r = mid-1;
            }
        }

        return dp[y][dir][x] = y-ans+max(sol(ans,x,0),sol(ans,x,1));
    }
}



void solve() {
    cin >> n >> m >> q;

    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        mxalf[i][0] = mxarg[i][0] = mp(a[i],i);
    }
    for(int i = 1; i <= m; i++) {
        cin >> b[i];
        mxblf[i][0] = mxbrg[i][0] = mp(b[i],i);
    }

    for(int pt = 1; pt <= 20; pt++) {
        for(int i = 1; i <= n; i++) {
            mxalf[i][pt] = max(mxalf[i][pt-1],mxalf[max(1LL,i-(1<<(pt-1)))][pt-1]);
        }
    }

    for(int pt = 1; pt <= 20; pt++) {
        for(int i = 1; i <= n; i++) {
            mxarg[i][pt] = max(mxarg[i][pt-1],mxarg[min(n,i+(1<<(pt-1)))][pt-1]);
        }
    }

    for(int pt = 1; pt <= 20; pt++) {
        for(int i = 1; i <= m; i++) {
            mxblf[i][pt] = max(mxblf[i][pt-1],mxblf[max(1LL,i-(1<<(pt-1)))][pt-1]);
        }
    }

    for(int pt = 1; pt <= 20; pt++) {
        for(int i = 1; i <= m; i++) {
            mxbrg[i][pt] = max(mxbrg[i][pt-1],mxbrg[min(m,i+(1<<(pt-1)))][pt-1]);
        }
    }

    while(q--) {
        int y,x;
        cin >> y >> x;
        cout << max({sol(y,x,0),sol(y,x,1),sol(y,x,2),sol(y,x,3)}) << endl;
    }

}

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(0);

    // freopen("in.in", "r", stdin);
    // freopen("out.out", "w", stdout);
    
    int tt = 1;
    // cin >> tt;
    while(tt--) {
        solve();
    }

}

Compilation message

abduction2.cpp: In function 'void solve()':
abduction2.cpp:158:74: error: no matching function for call to 'max(long long int, int)'
  158 |             mxalf[i][pt] = max(mxalf[i][pt-1],mxalf[max(1LL,i-(1<<(pt-1)))][pt-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: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:
abduction2.cpp:158:74: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
  158 |             mxalf[i][pt] = max(mxalf[i][pt-1],mxalf[max(1LL,i-(1<<(pt-1)))][pt-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: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:
abduction2.cpp:158:74: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
  158 |             mxalf[i][pt] = max(mxalf[i][pt-1],mxalf[max(1LL,i-(1<<(pt-1)))][pt-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: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:
abduction2.cpp:158:74: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  158 |             mxalf[i][pt] = max(mxalf[i][pt-1],mxalf[max(1LL,i-(1<<(pt-1)))][pt-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: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:
abduction2.cpp:158:74: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  158 |             mxalf[i][pt] = max(mxalf[i][pt-1],mxalf[max(1LL,i-(1<<(pt-1)))][pt-1]);
      |                                                                          ^
abduction2.cpp:170:74: error: no matching function for call to 'max(long long int, int)'
  170 |             mxblf[i][pt] = max(mxblf[i][pt-1],mxblf[max(1LL,i-(1<<(pt-1)))][pt-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: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:
abduction2.cpp:170:74: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
  170 |             mxblf[i][pt] = max(mxblf[i][pt-1],mxblf[max(1LL,i-(1<<(pt-1)))][pt-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: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:
abduction2.cpp:170:74: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
  170 |             mxblf[i][pt] = max(mxblf[i][pt-1],mxblf[max(1LL,i-(1<<(pt-1)))][pt-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: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:
abduction2.cpp:170:74: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  170 |             mxblf[i][pt] = max(mxblf[i][pt-1],mxblf[max(1LL,i-(1<<(pt-1)))][pt-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: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:
abduction2.cpp:170:74: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  170 |             mxblf[i][pt] = max(mxblf[i][pt-1],mxblf[max(1LL,i-(1<<(pt-1)))][pt-1]);
      |                                                                          ^