Submission #789319

#	Time	Username	Problem	Language	Result	Execution time	Memory
789319		fatemetmhr	Aliens (IOI16_aliens)	C++17	100 / 100	208 ms	10204 KiB

aliens

//  ~ Be Name Khoda ~  //

#include "aliens.h"
#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,Ofast")

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second

const int maxn  =  1e6   + 10;
const int maxn5 =  1e5   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   + 7;
const ll  inf   =  1e18;

int n;

vector <pair<ll, ll>> av;
pair <ll, int> dp[maxn5];

namespace cht{

    int pt = 0, best;
    pair <ll, pair<pair<ll, int>, ll>> a[maxn5]; // {st, {cons, shib}}
    ll last = inf;

    void clear(){
        pt = 0;
        best = 0;
        last = inf;
    }

    ll inter(pair <pair<ll, int>, ll> a, pair <pair<ll, int>, ll> b){
        if(b.se == a.se)
            return a.fi > b.fi ? inf : -inf;
        return (a.fi.fi - b.fi.fi) / (b.se - a.se) + ((a.fi.fi - b.fi.fi) % (b.se - a.se) > 0 || ((a.fi.fi - b.fi.fi) % (b.se - a.se) == 0 && b.fi.se < a.fi.se));
    }

    void add(pair<ll, int> cons, ll x){
        while(pt && inter(a[pt - 1].se, {cons, x}) <= a[pt - 1].fi)
            pt--;
        a[pt] = {-inf, {cons, x}};
        if(pt)
            a[pt].fi = inter(a[pt - 1].se, a[pt].se);
        pt++;
        //cout << "WA " << a[best + 1].fi << ' ' << a[pt - 1].fi << endl;
        //cout << "added " << pt << ' ' << best << ' ' << last << ' ' << a[pt - 1].fi << ' ' << a[best].fi << ' ' << a[best + 1].fi << ' ' << a[pt - 1].se.fi << ' ' << a[pt - 1].se.se << endl;
    }

    pair <ll, int> get_max(ll x){
        best = min(best, pt - 1);
        //cout << "here " << best << ' ' << a[best].fi << ' ' << x << endl;
        while(best + 1 < pt && a[best + 1].fi <= x)
            best++;
        //cout << "in " << x << ' ' << best << endl;
        return mp(a[best].se.fi.fi + a[best].se.se * x, a[best].se.fi.se);
    }
}

pair <ll, int> check(ll y){
    //cout << "********** " << x << endl;
    cht::clear();
    cht::add(mp(-(av[0].fi * av[0].fi), 0), av[0].fi);
    for(int i = 0; i < n; i++){
        auto ans = cht::get_max(2 * (av[i].se + 1));
        dp[i] = {(av[i].se + 1) * (av[i].se + 1) - ans.fi + y, (-ans.se) + 1};
        //cout << "hey " << i << ' ' << dp[x][i] << endl;
        if(i + 1 < n)
            cht::add(mp(-(dp[i].fi + av[i + 1].fi * av[i + 1].fi - (av[i].se >= av[i + 1].fi ? (av[i].se - av[i + 1].fi + 1) * (av[i].se - av[i + 1].fi + 1) : 0)), -dp[i].se), av[i + 1].fi);
    }
    return dp[n - 1];
}

vector <pair<int, int>> pt;
bool rem[maxn5];

long long take_photos(int N, int m, int k, std::vector<int> r, std::vector<int> c) {
    n = N;
    //*
    for(int i = 0; i < n; i++)
        pt.pb({min(r[i], c[i]), max(r[i], c[i])});
    sort(all(pt));
    for(int i = 0; i < n; i++){
        while(av.size() && av.back().fi == pt[i].fi && av.back().se <= pt[i].se)
            av.pop_back();
        if(av.size() && av.back().se >= pt[i].se)
            continue;
        av.pb(pt[i]);
    }
    n = av.size();
    //*/
    /*
    for(int i = 0; i < n; i++)
        cout << av[i].fi << ' ' << av[i].se << endl;
    //*/
    ll lo = -1, hi = inf;
    while(hi - lo > 1){
        ll mid = (lo + hi) >> 1;
        if(check(mid).se <= k)
            hi = mid;
        else
            lo = mid;
    }
    auto ans = check(hi);
    return ans.fi - hi * k;
}

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