Submission #530427

#	Time	Username	Problem	Language	Result	Execution time	Memory
530427		David_M	Aliens (IOI16_aliens)	C++14	Compilation error	0 ms	0 KiB

aliens

//#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define all(x) (x).begin(), (x).end()
#define F first
#define S second


deque<pair<pii, int> > dq;
int o;

bool check (int k, int b){
    auto [k0,b0]=dq[0].F;
    auto [k1,b1]=dq[1].F;

    //k1 * x + b1 = k0 * x + b0
    //(b0 - b1) / (k1 - k0)
    //k1 * x + b1 = k * x + b
    //(b - b1) / (k1 - k)

    //k < k0 < k1

    //(b - b1) / (k1 - k) > (b0 - b1) / (k1 - k0)
    //(b - b1) * (k1 - k0) - (b0 - b1) * (k1 - k) > 0

    return (b - b1) * (k1 - k0) - (b0 - b1) * (k1 - k) > 0;
}

void add(int k, int b, int cnt){
    while(dq.size()>1 && check(k, b))dq.pop_front(),o=max(o-1,0);
    dq.push_front({{k,b},cnt});
}

pii get(int i, ll x, ll C){
    auto [k,b]=dq[i].F;
    //cout<<"[i, k, b, x]: "<<i<<" "<<k<<" "<<b<<" "<<x<<endl;
    return {k*x+b, dq[i].S};
}

ll take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
    ll Ans=0;
    vector<pii> v, V(n);

    for (int i=0; i<n; i++){
        if(c[i]<r[i])swap(r[i], c[i]);
        V[i]={r[i], -c[i]};
    }

    sort(all(V));
    int rr=0;
    for (auto [l,r]:V){
        r*=-1;
        ////cout<<r<<endl;
        if(r>rr)v.pb({l,r+1});
        rr=max(r, rr);
    }
    V.clear();
    n=v.size();

    for (auto [l,r]:v){
        //cout<<"[l, r]: "<<l<<" "<<r<<endl;
    }

    ll L=0, R=1e18;
    while(L<=R){
        ll C=(L+R)>>1;
        vector<pii> dp(n+1);
        dp[0]={0,0};
        for (int i=1; i<=n; i++){
            auto &[ans, cnt]=dp[i];
            int r=v[i-1].S;
            ans=r*r+C;
            //cout<<"[ans]: "<<ans<<endl;
            cnt=1;
            int x=r;
            while(i>1 && get(o,x,C)>get(o+1,x,C))o++;

            if(i>1){
                auto [ans0, cnt0]=get(o,x,C);
                //cout<<"[o]: "<<o<<" "<<dq.size()<<endl;
                ans+=ans0;
                cnt+=cnt0;
            }

            if(i==n)continue;

            int l=v[i].F;
            add(-2*l, ans + l*l - max(0, r-l)*max(0, r-l), cnt);
        }
        for (auto [x, y]:dp){
            //cout<<"[dp]: "<<x<<" "<<y<<endl;
        }
        if(dp[n].S>k){
            L=C+1;
        }else{
            Ans=dp[n].F-dp[n].S*C;
            //cout<<"[C, Ans]: "<<C<<" "<<Ans<<endl;
            R=C-1;
        }
        dq.clear();
        o=0;
    }

    //dp + (r1-l)^2 - (r2-l)^2
    //dp + r1*r1 + l*l - 2*r1*l - (r2-l)^2
    //(-2*l) * r1 + (dp - r2*r2 + 2*r2*l)

    return Ans;
}
/*
int main() {
    int n, m, k;
    assert(3 == scanf("%d %d %d", &n, &m, &k));
    std::vector<int> r(n), c(n);
    for (int i = 0; i < n; i++) {
        assert(2 == scanf("%d %d", &r[i], &c[i]));
    }
    long long ans = take_photos(n, m, k, r, c);


    printf("%lld\n", ans);
    return 0;
}
*/

/*
5 7 2
0 3
4 4
4 6
4 5
4 6
*/

Compilation message (stderr)

aliens.cpp: In function 'bool check(long long int, long long int)':
aliens.cpp:17:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   17 |     auto [k0,b0]=dq[0].F;
      |          ^
aliens.cpp:18:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   18 |     auto [k1,b1]=dq[1].F;
      |          ^
aliens.cpp: In function 'void add(long long int, long long int, long long int)':
aliens.cpp:34:64: error: no matching function for call to 'max(long long int, int)'
   34 |     while(dq.size()>1 && check(k, b))dq.pop_front(),o=max(o-1,0);
      |                                                                ^
In file included 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 aliens.cpp:2:
/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:
aliens.cpp:34:64: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
   34 |     while(dq.size()>1 && check(k, b))dq.pop_front(),o=max(o-1,0);
      |                                                                ^
In file included 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 aliens.cpp:2:
/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:
aliens.cpp:34:64: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
   34 |     while(dq.size()>1 && check(k, b))dq.pop_front(),o=max(o-1,0);
      |                                                                ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from aliens.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:
aliens.cpp:34:64: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
   34 |     while(dq.size()>1 && check(k, b))dq.pop_front(),o=max(o-1,0);
      |                                                                ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from aliens.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:
aliens.cpp:34:64: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
   34 |     while(dq.size()>1 && check(k, b))dq.pop_front(),o=max(o-1,0);
      |                                                                ^
aliens.cpp: In function 'std::pair<long long int, long long int> get(long long int, long long int, long long int)':
aliens.cpp:39:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   39 |     auto [k,b]=dq[i].F;
      |          ^
aliens.cpp: In function 'long long int take_photos(long long int, long long int, long long int, std::vector<long long int>, std::vector<long long int>)':
aliens.cpp:55:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   55 |     for (auto [l,r]:V){
      |               ^
aliens.cpp:64:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   64 |     for (auto [l,r]:v){
      |               ^
aliens.cpp:74:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   74 |             auto &[ans, cnt]=dp[i];
      |                   ^
aliens.cpp:83:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   83 |                 auto [ans0, cnt0]=get(o,x,C);
      |                      ^
aliens.cpp:92:45: error: no matching function for call to 'max(int, long long int)'
   92 |             add(-2*l, ans + l*l - max(0, r-l)*max(0, r-l), cnt);
      |                                             ^
In file included 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 aliens.cpp:2:
/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:
aliens.cpp:92:45: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
   92 |             add(-2*l, ans + l*l - max(0, r-l)*max(0, r-l), cnt);
      |                                             ^
In file included 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 aliens.cpp:2:
/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:
aliens.cpp:92:45: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
   92 |             add(-2*l, ans + l*l - max(0, r-l)*max(0, r-l), cnt);
      |                                             ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from aliens.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:
aliens.cpp:92:45: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   92 |             add(-2*l, ans + l*l - max(0, r-l)*max(0, r-l), cnt);
      |                                             ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from aliens.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:
aliens.cpp:92:45: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   92 |             add(-2*l, ans + l*l - max(0, r-l)*max(0, r-l), cnt);
      |                                             ^
aliens.cpp:92:57: error: no matching function for call to 'max(int, long long int)'
   92 |             add(-2*l, ans + l*l - max(0, r-l)*max(0, r-l), cnt);
      |                                                         ^
In file included 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 aliens.cpp:2:
/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:
aliens.cpp:92:57: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
   92 |             add(-2*l, ans + l*l - max(0, r-l)*max(0, r-l), cnt);
      |                                                         ^
In file included 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 aliens.cpp:2:
/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:
aliens.cpp:92:57: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
   92 |             add(-2*l, ans + l*l - max(0, r-l)*max(0, r-l), cnt);
      |                                                         ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from aliens.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:
aliens.cpp:92:57: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   92 |             add(-2*l, ans + l*l - max(0, r-l)*max(0, r-l), cnt);
      |                                                         ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from aliens.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:
aliens.cpp:92:57: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   92 |             add(-2*l, ans + l*l - max(0, r-l)*max(0, r-l), cnt);
      |                                                         ^
aliens.cpp:94:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   94 |         for (auto [x, y]:dp){
      |                   ^