Submission #1300822

#	Time	Username	Problem	Language	Result	Execution time	Memory
1300822		papaulo	Pyramid Base (IOI08_pyramid_base)	C++20	Compilation error	0 ms	0 KiB

pyramid_base

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

#define int long long

#define MAXN 1000100
#define MAXP 400400

struct Node {
    int mn, sum;
    Node(int v) : mn(v), sum(v) {}
    Node() : Node(0) {}
    Node operator+(const Node &nd) {
        Node ans;
        ans.mn=min(mn, sum+nd.mn);
        ans.sum=this->sum+nd.sum;
        return ans;
    }
};
Node seg[4*MAXN];

int xx1[MAXP], yy1[MAXP], xx2[MAXP], yy2[MAXP];
int c[MAXP];
vector<pair<pair<int, int>, pair<int, int>>> vc1;
vector<pair<pair<int, int>, pair<int, int>>> vc2;
int m, n, p, b;

#define MP make_pair

int nid[MAXN];

void build(int n, int l, int r) {
    seg[n]=Node();
    if(l==r) nid[l]=n;
    else {
        int mid=(l+r)/2;
        build(2*n, l, mid);
        build(2*n+1, mid+1, r);
    }
}

void build() {
    build(1, 1, n);
}

void update(int i, int v) {
    if(i>n) return;
    int nd=nid[i];
    seg[nd]=Node(seg[nd].mn+v);
    while(nd>1) {
        int nn=nd/2;
        if(nd&1) {
            seg[nn]=seg[nd-1]+seg[nd];
        } else {
            seg[nn]=seg[nd]+seg[nd+1];
        }
        nd=nn;
    }
}

int test(int l) {
    vector<pair<pair<int, int>, pair<int, int>>> v1;
    vector<pair<pair<int, int>, pair<int, int>>> v2;
    n-=l-1;
    m-=l-1;
    build();
    for(auto pr : vc1) {
        v1.push_back(MP(MP(max(pr.first.first-l+1, 1), pr.first.second), MP(max(pr.second.first-l+1, 1), min(pr.second.second, n+1))));
    }
    for(auto pr : vc2) {
        v2.push_back(MP(MP(min(pr.first.first, m+1), pr.first.second), MP(max(pr.second.first-l+1, 1), min(pr.second.second, n+1))));
    }
    vector<pair<pair<int, int>, pair<int, int>>> vec(2*p);
    merge(v1.begin(), v1.end(), v2.begin(), v2.end(), vec.begin());
    int lst=1;
    for(auto pr : vec) {
        if(pr.first.first!=lst) {
            if(seg[1].mn<=b) {
                n+=l-1;
                m+=l-1;
                return 1;
            }
            lst=pr.first.first;
        }
        update(pr.second.first, pr.first.second);
        update(pr.second.second, -pr.first.second);
    }
    int ans=lst<=m;
    n+=l-1;
    m+=l-1;
    return ans;
}

int32_t main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cin >> m >> n >> b >> p;
    for(int i=0;i<p;i++) cin >> xx1[i] >> yy1[i] >> xx2[i] >> yy2[i] >> c[i];
    for(int i=0;i<p;i++) vc1.push_back(MP(MP(xx1[i], c[i]), MP(yy1[i], yy2[i]+1)));
    for(int i=0;i<p;i++) vc2.push_back(MP(MP(xx2[i]+1, -c[i]), MP(yy1[i], yy2[i]+1)));
    sort(vc1.begin(), vc1.end());
    sort(vc2.begin(), vc2.end());
    int l=0, r=min(m, n);
    while(l<r) {
        int mid=(l+r+1)/2;
        if(test(mid)) l=mid;
        else r=mid-1;
    }
    cout << l << endl;
}

Compilation message (stderr)

pyramid_base.cpp: In function 'long long int test(long long int)':
pyramid_base.cpp:68:31: error: no matching function for call to 'max(long long int, int)'
   68 |         v1.push_back(MP(MP(max(pr.first.first-l+1, 1), pr.first.second), MP(max(pr.second.first-l+1, 1), min(pr.second.second, n+1))));
      |                            ~~~^~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
                 from pyramid_base.cpp:1:
/usr/include/c++/13/bits/stl_algobase.h:257:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  257 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/13/bits/stl_algobase.h:257:5: note:   template argument deduction/substitution failed:
pyramid_base.cpp:68:31: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
   68 |         v1.push_back(MP(MP(max(pr.first.first-l+1, 1), pr.first.second), MP(max(pr.second.first-l+1, 1), min(pr.second.second, n+1))));
      |                            ~~~^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algobase.h:303:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  303 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/13/bits/stl_algobase.h:303:5: note:   template argument deduction/substitution failed:
pyramid_base.cpp:68:31: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
   68 |         v1.push_back(MP(MP(max(pr.first.first-l+1, 1), pr.first.second), MP(max(pr.second.first-l+1, 1), min(pr.second.second, n+1))));
      |                            ~~~^~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:61:
/usr/include/c++/13/bits/stl_algo.h:5795:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(initializer_list<_Tp>)'
 5795 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/13/bits/stl_algo.h:5795:5: note:   template argument deduction/substitution failed:
pyramid_base.cpp:68:31: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
   68 |         v1.push_back(MP(MP(max(pr.first.first-l+1, 1), pr.first.second), MP(max(pr.second.first-l+1, 1), min(pr.second.second, n+1))));
      |                            ~~~^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algo.h:5805:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(initializer_list<_Tp>, _Compare)'
 5805 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/13/bits/stl_algo.h:5805:5: note:   template argument deduction/substitution failed:
pyramid_base.cpp:68:31: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
   68 |         v1.push_back(MP(MP(max(pr.first.first-l+1, 1), pr.first.second), MP(max(pr.second.first-l+1, 1), min(pr.second.second, n+1))));
      |                            ~~~^~~~~~~~~~~~~~~~~~~~~~~
pyramid_base.cpp:68:80: error: no matching function for call to 'max(long long int, int)'
   68 |         v1.push_back(MP(MP(max(pr.first.first-l+1, 1), pr.first.second), MP(max(pr.second.first-l+1, 1), min(pr.second.second, n+1))));
      |                                                                             ~~~^~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algobase.h:257:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  257 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/13/bits/stl_algobase.h:257:5: note:   template argument deduction/substitution failed:
pyramid_base.cpp:68:80: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
   68 |         v1.push_back(MP(MP(max(pr.first.first-l+1, 1), pr.first.second), MP(max(pr.second.first-l+1, 1), min(pr.second.second, n+1))));
      |                                                                             ~~~^~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algobase.h:303:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  303 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/13/bits/stl_algobase.h:303:5: note:   template argument deduction/substitution failed:
pyramid_base.cpp:68:80: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
   68 |         v1.push_back(MP(MP(max(pr.first.first-l+1, 1), pr.first.second), MP(max(pr.second.first-l+1, 1), min(pr.second.second, n+1))));
      |                                                                             ~~~^~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algo.h:5795:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(initializer_list<_Tp>)'
 5795 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/13/bits/stl_algo.h:5795:5: note:   template argument deduction/substitution failed:
pyramid_base.cpp:68:80: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
   68 |         v1.push_back(MP(MP(max(pr.first.first-l+1, 1), pr.first.second), MP(max(pr.second.first-l+1, 1), min(pr.second.second, n+1))));
      |                                                                             ~~~^~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algo.h:5805:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(initializer_list<_Tp>, _Compare)'
 5805 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/13/bits/stl_algo.h:5805:5: note:   template argument deduction/substitution failed:
pyramid_base.cpp:68:80: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
   68 |         v1.push_back(MP(MP(max(pr.first.first-l+1, 1), pr.first.second), MP(max(pr.second.first-l+1, 1), min(pr.second.second, n+1))));
      |                                                                             ~~~^~~~~~~~~~~~~~~~~~~~~~~~
pyramid_base.cpp:71:78: error: no matching function for call to 'max(long long int, int)'
   71 |         v2.push_back(MP(MP(min(pr.first.first, m+1), pr.first.second), MP(max(pr.second.first-l+1, 1), min(pr.second.second, n+1))));
      |                                                                           ~~~^~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algobase.h:257:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  257 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/13/bits/stl_algobase.h:257:5: note:   template argument deduction/substitution failed:
pyramid_base.cpp:71:78: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
   71 |         v2.push_back(MP(MP(min(pr.first.first, m+1), pr.first.second), MP(max(pr.second.first-l+1, 1), min(pr.second.second, n+1))));
      |                                                                           ~~~^~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algobase.h:303:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  303 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/13/bits/stl_algobase.h:303:5: note:   template argument deduction/substitution failed:
pyramid_base.cpp:71:78: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
   71 |         v2.push_back(MP(MP(min(pr.first.first, m+1), pr.first.second), MP(max(pr.second.first-l+1, 1), min(pr.second.second, n+1))));
      |                                                                           ~~~^~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algo.h:5795:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(initializer_list<_Tp>)'
 5795 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/13/bits/stl_algo.h:5795:5: note:   template argument deduction/substitution failed:
pyramid_base.cpp:71:78: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
   71 |         v2.push_back(MP(MP(min(pr.first.first, m+1), pr.first.second), MP(max(pr.second.first-l+1, 1), min(pr.second.second, n+1))));
      |                                                                           ~~~^~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algo.h:5805:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(initializer_list<_Tp>, _Compare)'
 5805 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/13/bits/stl_algo.h:5805:5: note:   template argument deduction/substitution failed:
pyramid_base.cpp:71:78: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
   71 |         v2.push_back(MP(MP(min(pr.first.first, m+1), pr.first.second), MP(max(pr.second.first-l+1, 1), min(pr.second.second, n+1))));
      |                                                                           ~~~^~~~~~~~~~~~~~~~~~~~~~~~