Submission #228353

#	Time	Username	Problem	Language	Result	Execution time	Memory
228353		kuroni	Aliens (IOI16_aliens)	C++17	100 / 100	290 ms	5872 KiB

aliens

#include <bits/stdc++.h>
#include "aliens.h"
#define fi first
#define se second
using namespace std;

long long sqr(int x) {
    return 1LL * x * x;
}

struct line {
    int a;
    long long b;
    
    line(int _a, long long _b) : a(_a), b(_b) {}
    
    long long at(int x) {
        return 1LL * a * x + b;
    }
    
    double intersect(const line& oth) const {
        return 1.0 * (b - oth.b) / (oth.a - a);
    }
};

struct convex_hull {
    deque<pair<line, int>> de;
    
    void push(pair<line, int> cur) {
        while (de.size() >= 2) {
            double fit = de[de.size() - 2].fi.intersect(de[de.size() - 1].fi);
            double sit = de[de.size() - 2].fi.intersect(cur.fi);
            if (sit < fit && abs(sit - fit) >= 1E-6) {
                de.pop_back();
            } else {
                break;
            }
        }
        de.push_back(cur);
    }
    
    pair<long long, int> get_min(int x) {
        while (de.size() >= 2 && de[0].fi.at(x) > de[1].fi.at(x)) {
            de.pop_front();
        }
        int ans = de[0].se;
        for (int i = 1; i < de.size() && de[i].fi.at(x) == de[0].fi.at(x); i++) {
            ans = min(ans, de[i].se);
        }
        return {de[0].fi.at(x), ans + 1};
    }
};

pair<long long, int> solve(vector<pair<int, int>>& pos, long long c) {
    convex_hull cht;
    cht.push({line(-2 * pos[0].fi, sqr(pos[0].fi)), 0});
    for (int i = 0; i < (int)pos.size(); i++) {
        pair<long long, int> mi = cht.get_min(pos[i].se);
        mi.fi += c + 1LL * pos[i].se * pos[i].se;
        if (i == (int)pos.size() - 1) {
            return mi;
        } else {
            cht.push({line(-2 * pos[i + 1].fi, mi.fi + sqr(pos[i + 1].fi) -
                sqr(min(0, pos[i + 1].fi - pos[i].se))), mi.se});
        }
    }
}

long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
    vector<pair<int, int>> ini(n), pos;
    for (int i = 0; i < n; i++) {
        ini[i] = (r[i] < c[i] ? make_pair(r[i], c[i]) : make_pair(c[i], r[i]));
    }
    sort(ini.begin(), ini.end(), [](const pair<int, int> &u, const pair<int, int> &v) {
        return u.se < v.se || (u.se == v.se && u.fi > v.fi);
    });
    for (pair<int, int>& cur : ini) {
        cur.fi--;
        while (!pos.empty() && pos.back().fi >= cur.fi) {
            pos.pop_back();
        }
        pos.push_back(cur);
    }
    k = min(k, (int)pos.size());
    long long le = -1LL * m * m, ri = 1LL * m * m;
    while (le <= ri) {
        long long mi = (le + ri) / 2;
        pair<long long, int> ans = solve(pos, mi);
        if (ans.se <= k) {
            ri = mi - 1;
        } else {
            le = mi + 1;
        }
    }
    pair<long long, int> ans = solve(pos, le);
    return ans.fi - 1LL * k * le;
}

Compilation message (stderr)

aliens.cpp: In member function 'std::pair<long long int, int> convex_hull::get_min(int)':
aliens.cpp:47:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 1; i < de.size() && de[i].fi.at(x) == de[0].fi.at(x); i++) {
                         ~~^~~~~~~~~~~
aliens.cpp: In function 'std::pair<long long int, int> solve(std::vector<std::pair<int, int> >&, long long int)':
aliens.cpp:67:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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