#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=1e18;
struct Line{
mutable int k, m, p, cnt;
Line (int _k=0, int _m=0, int _p=0, int _cnt=0){ k=_k, m=_m, p=_p, cnt=_cnt; }
bool operator<(const Line &a) const { return k<a.k; }
bool operator<(int x) const { return p<x; }
};
struct LineContainer: vector<Line>{
int div(int x, int y){
return x/y-((x^y)<0 && (x%y));
}
bool isect(iterator x, iterator y){
if (y==end()) return x->p=inf, 0;
if (x->k==y->k) x->p=x->m>=y->m?inf:-inf;
else x->p=div(y->m-x->m, x->k-y->k);
return x->p>=y->p;
}
void add(int k, int m, int cnt){
k=-k, m=-m;
emplace_back(k, m, 0, cnt);
auto z=prev(end()), y=z++, x=y;
while (isect(y, z)) z=erase(z);
if (x!=begin() && isect(--x, y)) isect(x, erase(y));
while ((y=x)!=begin() && (--x)->p>=y->p) isect(x, erase(y));
}
int id=0;
pair<int, int> query(int x){
while (id+1<(int)size() && (*this)[id].k*x+(*this)[id].m<=(*this)[id+1].k*x+(*this)[id+1].m) ++id;
return {(-(*this)[id].k)*x+(-(*this)[id].m), (*this)[id].cnt};
}
};
long long take_photos(int32_t n, int32_t m, int32_t k, vector<int32_t> r, vector<int32_t> c) {
vector<pair<int, int>> v;
for (int i=0; i<n; ++i){
v.emplace_back(min(r[i], c[i]), max(r[i], c[i]));
}
sort(v.begin(), v.end());
vector<pair<int, int>> v2;
for (int i=0; i<(int)v.size(); ++i){
int j=i;
while (j+1<(int)v.size() && v[j+1].first==v[i].first) ++j;
if (v2.empty() || v2.back().second<v[j].second) v2.push_back(v[j]);
i=j;
}
n=v2.size();
for (auto &i:v2) ++i.second;
int L=0, R=1e9;
vector<pair<int, int>> f(n+1, {inf, inf});
LineContainer cht;
while (L<=R){
int mid=(L+R)>>1;
for (int i=0; i<=n; ++i) f[i]={inf, 0};
cht.clear();
cht.id=0;
f[0]={0, 0};
for (int i=1; i<=n; ++i){
int x=-2*v2[i-1].first, y=v2[i-1].first*v2[i-1].first;
if (i!=1 && v2[i-2].second>v2[i-1].first) y-=(v2[i-2].second-v2[i-1].first)*(v2[i-2].second-v2[i-1].first);
if (f[i-1].first!=inf) cht.add(x, y+f[i-1].first, f[i-1].second);
if (cht.size()){
auto tmp=cht.query(v2[i-1].second);
f[i]=min(f[i], {v2[i-1].second*v2[i-1].second+tmp.first+mid, tmp.second+1});
}
}
if (f[n].second<=k) R=mid-1;
else L=mid+1;
}
for (int i=0; i<=n; ++i) f[i]={inf, 0};
cht.clear();
cht.id=0;
f[0]={0, 0};
for (int i=1; i<=n; ++i){
int x=-2*v2[i-1].first, y=v2[i-1].first*v2[i-1].first;
if (i!=1 && v2[i-2].second>v2[i-1].first) y-=(v2[i-2].second-v2[i-1].first)*(v2[i-2].second-v2[i-1].first);
if (f[i-1].first!=inf) cht.add(x, y+f[i-1].first, f[i-1].second);
if (cht.size()){
auto tmp=cht.query(v2[i-1].second);
f[i]=min(f[i], {v2[i-1].second*v2[i-1].second+tmp.first+L, tmp.second+1});
}
}
return f[n].first-k*L;
// vector<vector<int>> f(n+1, vector<int>(k+1, inf));
// vector<LineContainer> cht(k);
// f[0][0]=0;
// for (int i=1; i<=n; ++i){
// int x=-2*v2[i-1].first, y=v2[i-1].first*v2[i-1].first;
// if (i!=1 && v2[i-2].second>v2[i-1].first) y-=(v2[i-2].second-v2[i-1].first)*(v2[i-2].second-v2[i-1].first);
// for (int j=1; j<=k; ++j){
// if (f[i-1][j-1]!=inf) cht[j-1].add(x, y+f[i-1][j-1]);
// if (cht[j-1].size()) f[i][j]=min(f[i][j], v2[i-1].second*v2[i-1].second+cht[j-1].query(v2[i-1].second));
// }
// }
// return *min_element(f[n].begin(), f[n].end());
}
Compilation message
chorus.cpp:1:10: fatal error: aliens.h: No such file or directory
1 | #include "aliens.h"
| ^~~~~~~~~~
compilation terminated.
