#include "aliens.h" #include <bits/stdc++.h> using namespace std; using ll = long long; using pll = pair<ll, ll>; // CHT const ll inf = 2e12; struct Line { mutable ll k, m, p, qtd; // AQUI (aqui mesmo) bool operator<(const Line& o) const { return k < o.k; } bool operator<(ll x) const { return p < x; } }; struct LineContainer : multiset<Line, less<>> { // (for doubles, use inf = 1/.0, div(a,b) = a/b) static const ll inf = LLONG_MAX; ll div(ll a, ll b) { // floored division return a / b - ((a ^ b) < 0 && a % b); } bool isect(iterator x, iterator y) { if (y == end()) return x->p = inf, 0; if (x->k == y->k) x->p = tie(x->m,x->qtd) > tie(y->m,y->qtd) ? inf : -inf; // AQUI (aqui mesmo) else x->p = div(y->m - x->m, x->k - y->k); return tie(x->p, x->qtd) >= tie(y->p, y->qtd); // AQUI (aqui mesmo) } void add(ll k, ll m, int qtd) { auto z = insert({ k, m, 0, qtd }), y = z++, x = y; while (isect(y, z)) z = erase(z); if (x != begin() && isect(--x, y)) isect(x, y = erase(y)); while ((y = x) != begin() && tie((--x)->p, x->qtd) >= tie(y->p, y->qtd)) isect(x, erase(y)); // AQUI (aqui mesmo) } pair<ll,ll> query(ll x) { // AQUI (aqui mesmo) assert(!empty()); auto l = *lower_bound(x); return {l.k * x + l.m, l.qtd}; // AQUI (aqui mesmo) } }; pair<ll, ll> solve(int n, vector<pair<ll, ll>> &ranges, ll x) { LineContainer lc; vector<pll> dp(n+1, {0, 0}); for (int i=n-1; i>=0; i--) { auto [li, ri] = ranges[i]; lc.add(2*(ri+1), -((ri+1)*(ri+1) + dp[i+1].first), -dp[i+1].second); auto [qry, jumps] = lc.query(li); dp[i] = {li*li - qry + x, -jumps+1}; if (i > 0 && ranges[i-1].second >= li) { dp[i].first -= (ranges[i-1].second-li+1)*(ranges[i-1].second-li+1); } } return dp[0]; } long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) { vector<pair<ll, ll>> ranges, tmp; for (int i=0; i<n; i++) { tmp.push_back({min(r[i], c[i]), -max(r[i], c[i])}); } sort(tmp.begin(), tmp.end()); for (auto [l, r]: tmp) { if (ranges.empty() || ranges.back().second < -r) { ranges.push_back({l, -r}); } } n = ranges.size(); k = min(k, n); ll lo = -inf, hi = inf; while (hi-lo > 1) { ll mid = (lo+hi)/2; auto [val, low] = solve(n, ranges, mid); if (low < k) { hi = mid; } else { lo = mid; } } auto [val, low] = solve(n, ranges, lo); return val - k*lo; }

aliens.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
aliens_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~