Submission #712889

#	Time	Username	Problem	Language	Result	Execution time	Memory
712889		minhnhatnoe	Aliens (IOI16_aliens)	C++14	100 / 100	1116 ms	11364 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll sq(ll a) {return a * a;}
struct lichao_tree{
    struct node{
        pair<ll, ll> line;
        int cnt = 0;
        int l = -1, r = -1;
        node(ll a, ll b, int cnt): line(a, b), cnt(cnt) {}
        ll eval(ll x){
            return line.first * x + line.second;
        }
    };
    int L, R;
    lichao_tree(int lrange, int rrange): L(lrange), R(rrange) {}
    vector<node> g;
    void insert(ll a, ll b, int cnt){
        if (g.size() == 0){
            g.emplace_back(a, b, cnt);
            return;
        }
        int tidx = 0;
        int tl = L, tr = R;
        node tmp(a, b, cnt);
        while (true){
            int tm = (tl + tr)>>1;
            bool left = g[tidx].eval(tl) > tmp.eval(tl);
            bool mid = g[tidx].eval(tm) > tmp.eval(tm);
            if (mid){
                swap(g[tidx].line, tmp.line);
                swap(g[tidx].cnt, tmp.cnt);
            }
            if (tl == tr) return;
            if (left != mid){
                if (g[tidx].l == -1){
                    g[tidx].l = g.size();
                    g.emplace_back(tmp);
                    return;
                }
                tidx = g[tidx].l;
                tr = tm;
            }
            else{
                if (g[tidx].r == -1){
                    g[tidx].r = g.size();
                    g.emplace_back(tmp);
                    return;
                }
                tidx = g[tidx].r;
                tl = tm+1;
            }
        }
    }
    pair<ll, int> query(int pos){
        pair<ll, int> result(LLONG_MAX, -1);
        assert((g.size()));
        int tidx = 0;
        int tl = L, tr = R;
        while (tidx != -1){
            result = min(result, make_pair(g[tidx].eval(pos), g[tidx].cnt));
            int tm = (tl + tr) >> 1;
            if (pos <= tm){
                tidx = g[tidx].l;
                tr = tm;
            }
            else{
                tidx = g[tidx].r;
                tl = tm+1;
            }
        }
        return result;
    }
};
pair<ll, int> alien_solve(const vector<pair<ll, ll>> &p, ll cost){
    lichao_tree tree(0, 2000000);
    pair<ll, int> result(0, 0);
    for (int i=0; i<p.size(); i++){
        ll intersect = i ? sq(max(0LL, p[i-1].second - p[i].first + 1)) : 0;
        tree.insert(-2 * p[i].first, result.first + sq(p[i].first) - intersect, result.second+1);
        result = tree.query(p[i].second + 1);
        result.first += sq(p[i].second + 1) + cost;
    }
    return result;
}
vector<pair<ll, ll>> simplify(vector<pair<ll, ll>> &p){
    sort(p.begin(), p.end(), [](const pair<ll, ll> &a, const pair<ll, ll> &b){
        return make_pair(a.first, -a.second) < make_pair(b.first, -b.second);
    });
    vector<pair<ll, ll>> r; r.reserve(p.size());
    for (const pair<ll, ll> &a: p){
        if (r.size() && a.second <= r.back().second) continue;
        r.push_back(a);
    }
    return r;
}
ll take_photos(int n, int m, int k, vector<int> r, vector<int> c){
    vector<pair<ll, ll>> p(n);
    for (int i=0; i<n; i++)
        p[i] = minmax(r[i], c[i]);
    p = simplify(p);
    ll bl = 0, br = 1e18;
    while (bl < br){
        ll bm = (bl + br)>>1;
        if (alien_solve(p, bm).second > k) bl = bm + 1;
        else br = bm;
    }
    pair<ll, int> result = alien_solve(p, bl);
    return result.first - k * bl;
}

Compilation message (stderr)

aliens.cpp: In function 'std::pair<long long int, int> alien_solve(const std::vector<std::pair<long long int, long long int> >&, ll)':
aliens.cpp:80:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |     for (int i=0; i<p.size(); i++){
      |                   ~^~~~~~~~~

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