Submission #531292

#	Time	Username	Problem	Language	Result	Execution time	Memory
531292		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 ll long long
#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(x) (x).begin(), (x).end()
#define F first
#define S second


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

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

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

void add(ll k, ll 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;
    return {k*x+b, dq[i].S};
}

void calc_dp(int n, vector<pll> v, vector<pll> &dp, ll C){
    dp[0]={0,0};
    add(-2*v[0].F, v[0].F*v[0].F, 0);
    for (int i=1; i<=n; i++){
        auto &[ans, cnt]=dp[i];
        ll r=v[i-1].S;
        ans=r*r+C;
        cnt=1;
        ll x=r;
        while(i>1 && get(o,x,C)>get(o+1,x,C))o++;

        auto [ans0, cnt0]=get(o,x,C);
        ans+=ans0;
        cnt+=cnt0;

        if(i==n)continue;

        ll l=v[i].F;
        add(l*-2, ans + l*l - max((ll)0, r-l)*max((ll)0, r-l), cnt);
    }
}


ll take_photos(int n, ll m, ll k, vector<int> r, vector<int> c) {
    ll Ans=0;
    vector<pll> 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));
    ll rr=-1;
    for (auto [l,r]:V){
        r*=-1;
        if(r>rr)v.pb({l,r+1});
        rr=max(r, rr);
    }
    V.clear();
    n=v.size();

    ll L=0, R=m*m;
    while(L<=R){
        ll C=L+R>>1;
        vector<pll> dp(n+1);
        calc_dp(n, v, dp, C);
        if(dp[n].S>k){
            L=C+1;
        }else{
            Ans=dp[n].F;
            R=C-1;
        }
        dq.clear();
        o=0;
    }

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


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

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

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

void add(ll k, ll 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;
    return {k*x+b, dq[i].S};
}

void calc_dp(int n, vector<pll> v, vector<pll> &dp, ll C){
    dp[0]={0,0};
    add(-2*v[0].F, v[0].F*v[0].F, 0);
    for (int i=1; i<=n; i++){
        auto &[ans, cnt]=dp[i];
        ll r=v[i-1].S;
        ans=r*r+C;
        cnt=1;
        ll x=r;
        while(i>1 && get(o,x,C)>get(o+1,x,C))o++;

        auto [ans0, cnt0]=get(o,x,C);
        ans+=ans0;
        cnt+=cnt0;

        if(i==n)continue;

        ll l=v[i].F;
        add(l*-2, ans + l*l - max((ll)0, r-l)*max((ll)0, r-l), cnt);
    }
}


ll take_photos(int n, ll m, ll k, vector<int> r, vector<int> c) {
    ll Ans=0;
    vector<pll> 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));
    ll rr=-1;
    for (auto [l,r]:V){
        r*=-1;
        if(r>rr)v.pb({l,r+1});
        rr=max(r, rr);
    }
    V.clear();
    n=v.size();

    ll L=0, R=m*m;
    while(L<=R){
        ll C=L+R>>1;
        vector<pll> dp(n+1);
        calc_dp(n, v, dp, C);
        if(dp[n].S>k){
            L=C+1;
        }else{
            Ans=dp[n].F;
            R=C-1;
        }
        dq.clear();
        o=0;
    }

    return Ans-k*L;
}

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 'std::pair<int, int> get(int, long long int, long long int)':
aliens.cpp:29:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   29 |     auto [k,b]=dq[i].F;
      |          ^
aliens.cpp: In function 'void calc_dp(int, std::vector<std::pair<long long int, long long int> >, std::vector<std::pair<long long int, long long int> >&, long long int)':
aliens.cpp:37:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   37 |         auto &[ans, cnt]=dp[i];
      |               ^
aliens.cpp:44:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   44 |         auto [ans0, cnt0]=get(o,x,C);
      |              ^
aliens.cpp: In function 'long long int take_photos(int, long long int, long long int, std::vector<int>, std::vector<int>)':
aliens.cpp:67:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   67 |     for (auto [l,r]:V){
      |               ^
aliens.cpp:77:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   77 |         ll C=L+R>>1;
      |              ~^~
aliens.cpp: At global scope:
aliens.cpp:103:24: error: redefinition of 'std::deque<std::pair<std::pair<long long int, long long int>, int> > dq'
  103 | deque<pair<pll, int> > dq;
      |                        ^~
aliens.cpp:13:24: note: 'std::deque<std::pair<std::pair<long long int, long long int>, int> > dq' previously declared here
   13 | deque<pair<pll, int> > dq;
      |                        ^~
aliens.cpp:104:5: error: redefinition of 'int o'
  104 | int o;
      |     ^
aliens.cpp:14:5: note: 'int o' previously declared here
   14 | int o;
      |     ^
aliens.cpp:106:6: error: redefinition of 'bool check(long long int, long long int)'
  106 | bool check (ll k, ll b){
      |      ^~~~~
aliens.cpp:16:6: note: 'bool check(long long int, long long int)' previously defined here
   16 | bool check (ll k, ll b){
      |      ^~~~~
aliens.cpp: In function 'bool check(long long int, long long int)':
aliens.cpp:107:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  107 |     auto [k0,b0]=dq[0].F;
      |          ^
aliens.cpp:108:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  108 |     auto [k1,b1]=dq[1].F;
      |          ^
aliens.cpp: At global scope:
aliens.cpp:113:6: error: redefinition of 'void add(long long int, long long int, int)'
  113 | void add(ll k, ll b, int cnt){
      |      ^~~
aliens.cpp:23:6: note: 'void add(long long int, long long int, int)' previously defined here
   23 | void add(ll k, ll b, int cnt){
      |      ^~~
aliens.cpp:118:5: error: redefinition of 'std::pair<int, int> get(int, long long int, long long int)'
  118 | pii get(int i, ll x, ll C){
      |     ^~~
aliens.cpp:28:5: note: 'std::pair<int, int> get(int, long long int, long long int)' previously defined here
   28 | pii get(int i, ll x, ll C){
      |     ^~~
aliens.cpp: In function 'std::pair<int, int> get(int, long long int, long long int)':
aliens.cpp:119:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  119 |     auto [k,b]=dq[i].F;
      |          ^
aliens.cpp: At global scope:
aliens.cpp:123:6: error: redefinition of 'void calc_dp(int, std::vector<std::pair<long long int, long long int> >, std::vector<std::pair<long long int, long long int> >&, long long int)'
  123 | void calc_dp(int n, vector<pll> v, vector<pll> &dp, ll C){
      |      ^~~~~~~
aliens.cpp:33:6: note: 'void calc_dp(int, std::vector<std::pair<long long int, long long int> >, std::vector<std::pair<long long int, long long int> >&, long long int)' previously defined here
   33 | void calc_dp(int n, vector<pll> v, vector<pll> &dp, ll C){
      |      ^~~~~~~
aliens.cpp: In function 'void calc_dp(int, std::vector<std::pair<long long int, long long int> >, std::vector<std::pair<long long int, long long int> >&, long long int)':
aliens.cpp:127:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  127 |         auto &[ans, cnt]=dp[i];
      |               ^
aliens.cpp:134:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  134 |         auto [ans0, cnt0]=get(o,x,C);
      |              ^
aliens.cpp: At global scope:
aliens.cpp:146:4: error: redefinition of 'long long int take_photos(int, long long int, long long int, std::vector<int>, std::vector<int>)'
  146 | ll take_photos(int n, ll m, ll k, vector<int> r, vector<int> c) {
      |    ^~~~~~~~~~~
aliens.cpp:56:4: note: 'long long int take_photos(int, long long int, long long int, std::vector<int>, std::vector<int>)' previously defined here
   56 | ll take_photos(int n, ll m, ll k, vector<int> r, vector<int> c) {
      |    ^~~~~~~~~~~
aliens.cpp: In function 'long long int take_photos(int, long long int, long long int, std::vector<int>, std::vector<int>)':
aliens.cpp:157:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  157 |     for (auto [l,r]:V){
      |               ^
aliens.cpp:167:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  167 |         ll C=L+R>>1;
      |              ~^~