Submission #1082653

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

aliens

#include "aliens.h"
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <ll,ll> pll;
typedef pair <int,int> pii;
typedef pair <int,pii> piii;
 
#define forr(_a,_b,_c) for(int _a = (_b); _a <= int (_c); ++_a)
#define ford(_a,_b,_c) for(int _a = (_b) + 1; _a --> int (_c);)
#define forf(_a,_b,_c) for(int _a = (_b); _a < int (_c); ++_a)
#define st first
#define nd second
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define mask(i) (1LL << (i))
#define bit(x, i) (((x) >> (i)) & 1)
#define bp __builtin_popcountll
#define file "test"
 
template<class X, class Y>
    bool minz(X &x, const Y &y) {
        if (x > y) {
            x = y;
            return true;
        } return false;
    }
template<class X, class Y>
    bool maxz(X &x, const Y &y) {
        if (x < y) {
            x = y;
            return true;
        } return false;
    }
 
const int N = 1e6 + 5;
const ll oo = (ll) 1e16;
const ll mod = 1e9 + 7; // 998244353;
 
struct line {
    ll m, c;
    ll eval (ll x) { return m * x + c; }
    ld its (line l) { return (ld) (c - l.c) / (l.m - m); }
};
 
ll sqr (ll x){
    return x * x;
}
 
ll dp[N], cnt[N];
vector <pll> v;
map <ll, ll> z;
 
void calc (ll x){
    deque <line> dq;
    deque <int> dqcnt;
    dq.push_front({-2 * v[0].st, x + 1 + sqr(v[0].st) - 2 * v[0].st});
    dqcnt.push_front(0);
    
    forf (i, 0, v.size()){
        while (dq.size() >= 2 && dq.back().eval(v[i].nd) > dq[dq.size() - 2].eval(v[i].nd)){
            dq.pop_back();
            dqcnt.pop_back();
        }
    
        dp[i] = dq.back().eval(v[i].nd) + sqr(v[i].nd) + 2 * v[i].nd;
        cnt[i] = cnt[dqcnt.back()] + 1;
 
        line cur = {-2 * v[i].st, dp[i] + x + 1 - sqr(max(0ll, v[i].nd - v[i + 1].st + 1)) 
            + sqr(v[i + 1].st) - 2 * v[i + 1].st};
 
        while (dq.size() >= 2 && cur.its(dq[0]) >= dq[0].its(dq[1])){
            dq.pop_front();
        	dqcnt.pop_front();
        }
        dqcnt.push_front(cnt);
        dq.push_front(cur);
    }
}
 
ll take_photos (int n, int m, int k, vector<int> r, vector<int> c){
    forf (i, 0, n){
        if (r[i] > c[i]) swap(r[i], c[i]);
        maxz(z[r[i]], c[i]);
    }
 
    ll mx = 0;
    for (pll t : z){
        if (t.nd > mx){
            v.pb(t);
            mx = t.nd;
        }
    }
    
    ll l = 0, h = 1ll * m * m;
    n = v.size() - 1;
 
    // for (pii t : v)
    //     cout << t.st << " " << t.nd << "\n";
 
    while (l < h){
        ll mid = (l + h) >> 1;
        calc(mid);
        //cout << mid << " " << cnt[n] << endl;
        if (cnt[n] > k)
            l = mid + 1;
        else h = mid;
    } 
 
    calc(l);
 
    //cout << dp[n] << " " << cnt[n] << " " << l << endl;; 
    
    return dp[n] - k * l;
}

Compilation message (stderr)

aliens.cpp: In function 'void calc(ll)':
aliens.cpp:78:29: error: no matching function for call to 'push_front(ll [1000005])'
   78 |         dqcnt.push_front(cnt);
      |                             ^
In file included from /usr/include/c++/10/deque:67,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:68,
                 from aliens.cpp:2:
/usr/include/c++/10/bits/stl_deque.h:1456:7: note: candidate: 'void std::deque<_Tp, _Alloc>::push_front(const value_type&) [with _Tp = int; _Alloc = std::allocator<int>; std::deque<_Tp, _Alloc>::value_type = int]' (near match)
 1456 |       push_front(const value_type& __x)
      |       ^~~~~~~~~~
/usr/include/c++/10/bits/stl_deque.h:1456:7: note:   conversion of argument 1 would be ill-formed:
aliens.cpp:78:26: error: invalid conversion from 'll*' {aka 'long long int*'} to 'std::deque<int>::value_type' {aka 'int'} [-fpermissive]
   78 |         dqcnt.push_front(cnt);
      |                          ^~~
      |                          |
      |                          ll* {aka long long int*}
In file included from /usr/include/c++/10/deque:67,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:68,
                 from aliens.cpp:2:
/usr/include/c++/10/bits/stl_deque.h:1471:7: note: candidate: 'void std::deque<_Tp, _Alloc>::push_front(std::deque<_Tp, _Alloc>::value_type&&) [with _Tp = int; _Alloc = std::allocator<int>; std::deque<_Tp, _Alloc>::value_type = int]' (near match)
 1471 |       push_front(value_type&& __x)
      |       ^~~~~~~~~~
/usr/include/c++/10/bits/stl_deque.h:1471:7: note:   conversion of argument 1 would be ill-formed:
aliens.cpp:78:26: error: invalid conversion from 'll*' {aka 'long long int*'} to 'std::deque<int>::value_type' {aka 'int'} [-fpermissive]
   78 |         dqcnt.push_front(cnt);
      |                          ^~~
      |                          |
      |                          ll* {aka long long int*}