Submission #413281

#	Time	Username	Problem	Language	Result	Execution time	Memory
413281		ja_kingy	Aliens (IOI16_aliens)	C++14	100 / 100	311 ms	10512 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<ll,ll> pii;
 
const int mxN = 1e5;
vector<int> stk;
ll n, m, k, dp[mxN], pho[mxN], bst, l[mxN], r[mxN];
 
ll sqr(ll x) {return x*x;}
 
struct line {ll m, c, pcnt;};
vector<line> lines;
long double sect(line a, line b) {return (long double)(a.m - b.m) / (b.c - a.c);}
const long double EPS = 1e-15;
 
ll eval(line l, ll x) {return l.m*x + l.c;}
 
void upd(line l) {
    while (lines.size() > 1 && sect(l, lines[lines.size()-2]) < sect(l, lines.back())) {
        lines.pop_back();
    }
    while (lines.size() > 1 && fabs(sect(l, lines[lines.size()-2]) - sect(l, lines.back())) < EPS && l.pcnt <= lines.back().pcnt) {
        lines.pop_back();
    }
    lines.push_back(l);
    bst = min(bst, (ll)lines.size()-1);
}
 
line qry(ll x) {
    while (bst < lines.size()-1 && ((eval(lines[bst+1], x) < eval(lines[bst], x)) || (eval(lines[bst+1], x) == eval(lines[bst], x) && lines[bst+1].pcnt <= lines[bst].pcnt))) bst++;
    return lines[bst];
}
 
int slv(ll cst) {
    lines.clear();
    upd({-2*l[stk[0]], sqr(l[stk[0]]), 0});
    for (int i = 0; i < stk.size(); ++i) {
        ll ri = r[stk[i]]+1;
        line res = qry(ri);
        dp[i] = cst + sqr(ri) + eval(res, ri);
        pho[i] = res.pcnt + 1;
        if (i+1 < stk.size()) upd({-2*l[stk[i+1]], dp[i] - sqr(max(0ll,ri-l[stk[i+1]])) + sqr(l[stk[i+1]]), pho[i]});
    }
    return pho[stk.size() - 1];
}
 
ll take_photos(int N, int m, int k, vector<int> R, vector<int> C) {
    n = N;
    for (int i = 0; i < n; ++i) {
        l[i] = min(R[i], C[i]);
        r[i] = max(R[i], C[i]);
    }
    vector<int> order(n);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int a, int b){return r[a] < r[b];});
    for (int i: order) {
        while (stk.size() && l[stk.back()] >= l[i]) stk.pop_back();
        stk.push_back(i);
    }
    ll lo = 0, hi = (ll)m*m, mid;
    while (lo != hi) {
        mid = lo+hi>>1;
        if (slv(mid) <= k) hi = mid;
        else lo = mid + 1;
    }
    slv(lo);
    return dp[stk.size()-1] - k*lo;
}

Compilation message (stderr)

aliens.cpp: In function 'line qry(ll)':
aliens.cpp:33:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     while (bst < lines.size()-1 && ((eval(lines[bst+1], x) < eval(lines[bst], x)) || (eval(lines[bst+1], x) == eval(lines[bst], x) && lines[bst+1].pcnt <= lines[bst].pcnt))) bst++;
      |            ~~~~^~~~~~~~~~~~~~~~
aliens.cpp: In function 'int slv(ll)':
aliens.cpp:40:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for (int i = 0; i < stk.size(); ++i) {
      |                     ~~^~~~~~~~~~~~
aliens.cpp:45:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         if (i+1 < stk.size()) upd({-2*l[stk[i+1]], dp[i] - sqr(max(0ll,ri-l[stk[i+1]])) + sqr(l[stk[i+1]]), pho[i]});
      |             ~~~~^~~~~~~~~~~~
aliens.cpp: In function 'll take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:65:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |         mid = lo+hi>>1;
      |               ~~^~~

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