Submission #745380

# Submission time Handle Problem Language Result Execution time Memory
745380 2023-05-19T23:00:29 Z Lobo Painting Walls (APIO20_paint) C++17
Compilation error
0 ms 0 KB
#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define all(x) x.begin(),x.end()
const int maxn = 2e5+10;
const int inf = 1e9+10;

int minimumInstructions(int n, int m, int k, vector<int> c,vector<int> a, vector<vector<int>> b) {
    vector<int> f[k];
    for(int i = 0; i < m; i++) {
        sort(all(b[i]));
        for(auto x : b[i]) {
            f[x].pb(i);
        }
    }

    vector<pair<int,int>> pos;
    for(int i = n-1; i >= 0; i-= max(1LL,m/2)) {
        for(auto j : f[c[i]]) {
            int cnt;
            int li = i;
            int lj = j;
            cnt = 0;
            while(cnt++ <= m) {
                if(li < 0 || b[lj].back() < c[li] || *lower_bound(all(b[lj]),c[li]) != c[li]) {
                    li++;
                    break;
                }
                li--;
                lj--;
                lj = (lj%m+m)%m;
            }

            int ri = i;
            int rj = j;
            cnt = 0;
            while(cnt++ <= m) {
                if(ri > n-1 || b[rj].back() < c[ri] || *lower_bound(all(b[rj]),c[ri]) != c[ri]) {
                    ri--;
                    break;
                }
                ri++;
                rj++;
                rj = (rj%m+m)%m;
            }
            pos.pb(mp(li,ri));
            // cout << i << " " << j << " " << li << " " << ri << endl;
        }
    }

    sort(all(pos));

    vector<pair<int,int>> pos1;
    for(auto X : pos) {
        while(pos1.size() && pos1.back().fr == X.fr) pos1.pop_back();
        if(pos1.size() && pos1.back().sc >= X.sc) continue;
        pos1.pb(X);
    }
    swap(pos,pos1);
    reverse(all(pos));
    for(auto x : pos) {
        // cout << x.fr << " " << x.sc << endl;
    }
    vector<int> dp(n+1,inf);
    dp[0] = 0;
    priority_queue<pair<int,int>> pq;
    pq.push(mp(0,0));
    pq.push(mp(-inf,n));
    for(int i = 0; i <= n; i++) {
        while(pq.top().sc < i) pq.pop();
        dp[i] = -pq.top().fr;
        if(dp[i] == inf) continue;
        while(pos.size() && pos.back().sc < i+m-1) pos.pop_back();
        if(pos.empty() || pos.back().fr > i) continue;
        pq.push(mp(-(dp[i]+1),i+m));
    }

    if(dp[n] == inf) return -1;
    return dp[n];
}

Compilation message

paint.cpp: In function 'int minimumInstructions(int, int, int, std::vector<int>, std::vector<int>, std::vector<std::vector<int> >)':
paint.cpp:22:45: error: no matching function for call to 'max(long long int, int)'
   22 |     for(int i = n-1; i >= 0; i-= max(1LL,m/2)) {
      |                                             ^
In file included from /usr/include/c++/10/vector:60,
                 from paint.h:1,
                 from paint.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:
paint.cpp:22:45: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
   22 |     for(int i = n-1; i >= 0; i-= max(1LL,m/2)) {
      |                                             ^
In file included from /usr/include/c++/10/vector:60,
                 from paint.h:1,
                 from paint.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:
paint.cpp:22:45: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
   22 |     for(int i = n-1; i >= 0; i-= max(1LL,m/2)) {
      |                                             ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from paint.cpp:2:
/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:
paint.cpp:22:45: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
   22 |     for(int i = n-1; i >= 0; i-= max(1LL,m/2)) {
      |                                             ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from paint.cpp:2:
/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:
paint.cpp:22:45: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
   22 |     for(int i = n-1; i >= 0; i-= max(1LL,m/2)) {
      |                                             ^