Submission #957387

#	Time	Username	Problem	Language	Result	Execution time	Memory
957387		ZeroCool	Aliens (IOI16_aliens)	C++17	100 / 100	916 ms	22596 KiB

aliens

//* Nigga we hit em up like motherfucking Tupac Shakur
 
#include "aliens.h"
#include <bits/stdc++.h>
 
using ll = long long;
 
using namespace std;
 
const ll N = 1e6 + 10;
 
using ld = long double;
 
#define pb push_back
#define all(v) v.begin(), v.end()
 
ll n, m, k;
 
vector<pair<ll,ll> > v, x;
ll ans;
pair<ll,ll> dp[N];
ll L[N];
ll R[N];
ll cnt[N];
 
struct Line{
    ll k, b;
    ll id;
    ll operator ()(ll x) {
        return k * x + b;
    }
};
 
vector<Line> st;
 
ld cross(Line x, Line y){
    return (ld)(x.b - y.b) / (ld)(y.k - x.k);
}
 
void insert(Line nv){
    ll m = st.size();
    while(st.size() > 1 && cross(nv, st[m-1]) <= cross(st[m-1], st[m-2])){
        st.pop_back();
        --m;
    }
    st.pb(nv);
}
 
pair<ll,ll> query(ll x){
    ll l = -1;
    ll r = st.size() - 1;
    while(r - l  > 1){
        ll mid = (l + r) / 2;
        if(cross(st[mid], st[mid+1]) > x)r = mid;
        else l = mid;
    }
    //++r;
    return {st[r](x), st[r].id};
}
 
pair<ll,ll> f(ll C){
    st.clear();
    dp[0] = {0, 0};
    for(ll i = 1;i<=n;i++){
        insert({-L[i], dp[i-1].first + L[i] * L[i] - max(R[i-1] - L[i], 0ll) * max(0ll, R[i-1] - L[i]) + C, i -1});
        pair<ll,ll> q = query(2 * R[i]);
        dp[i].first = q.first + R[i] * R[i];
        dp[i].second = dp[q.second].second + 1;
    }
    return dp[n];
}
 
long long take_photos(int nn, int mm, int kk, std::vector<int> rr, std::vector<int> cc) {
    n = nn;
    m = mm;
    k = kk;
    for(ll i = 1;i<=n;i++){
        ll l = rr[i-1];
        ll r = cc[i-1];
        l++, r++;
        if(l > r)swap(l, r);
        v.pb({l, -r});
    }
    sort(all(v));
    ll mx = 0;
    x.pb({0, 0});
    for(auto [l, r] : v){
        r = -r;
        if(r > mx){
            mx = r;
            x.pb({l, r});
        }
    }
    sort(all(x));
    n = x.size() - 1;
    
    for(ll i = 1;i<=n;i++){
        L[i] = x[i].first - 1;
        R[i] = x[i].second;
    }
    ll l = -1;
    ll r = 1e15;
    ll ans = m * m;
    k = min(n, k);
    while(r - l > 1){
        ll mid = (l + r) / 2;
        if(f(mid).second > k){
            l = mid;
        }else{
            r = mid;
        }
    }
    //cout<<ans<<endl;
    pair<ll,ll> p = f(l);
    return p.first - k * l;
}
 

Compilation message (stderr)

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:103:8: warning: unused variable 'ans' [-Wunused-variable]
  103 |     ll ans = m * m;
      |        ^~~

• Subtask 1: 4 / 4
• Subtask 2: 12 / 12
• Subtask 3: 9 / 9
• Subtask 4: 16 / 16
• Subtask 5: 19 / 19
• Subtask 6: 40 / 40