#include <iostream>
#include <vector>
#include <set>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <stdio.h>
#include <cmath>
//#include <queue>
//#include <string>
//#include <map>
//#include <complex>
//#include <chrono>
//#include <random>
//#include <stack>
//#include <set>
//#include <fstream>
#define FOR(i,n) for(int i = 0;i < n; i++)
#define FORE(i,a,b) for(int i = a; i <= b ; i++)
#define ss second
#define ff first
#define ll long long int
#define ii pair<ll,ll>
#define il pair<int,ll>
#define li pair<ll,int>
#define x ff
#define y ss
#define lii pair<ll,pair<int,int> >
#define piil pair<int ,pair<int,int> >
#define iii pair<pair<int,int>,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define pb push_back
#define mp make_pair
#include "aliens.h"
using namespace std;
const ll INF = 1e18;
vector<ii> all;
vector<ii> reduceList(vector<ii> v){
sort(v.begin(), v.end());
vector<ii> res;
ll mx = 0;
for(auto e:v){
if(res.empty())res.pb(e);
else if(res.back().ff < e.ff){
if(e.ss > mx)res.pb(e);
}else{
res.back() = e;
}
mx = max(mx,e.ss);
}
return res;
}
vector<ii> createRanges(vi r,vi c,int n){
vector<ii> all;
FOR(i,n)all.pb({min(r[i],c[i]),max(r[i],c[i])});
return all;
}
ll C1[50*1000+1];
void prec(){
C1[0] = 0;
FORE(i,1,(int)all.size()-1){
C1[i] = max((ll)0,all[i-1].ss - all[i].ff+1);
C1[i] *= C1[i];
}
}
ll cost(int t,int i){
i--;
ll t1 = all[i].ss - all[t].ff + 1; t1*=t1;
ll t2 = C1[t];
return t1 - t2;
}
struct Node{
int left;
int right;
pll p;
Node(){
left = -1;
right = -1;
p = {1e9,1e9};
}
void init(){
left = -1;
right = -1;
p = {1e9,1e9};
}
};
Node B[500*100*100];
int PTR = 0;
inline int get(){
//cout << PTR << endl;
B[PTR].init();
//cout << "wow" << endl;
return PTR++;
}
class Segtree{
int n;
int head;
inline void expand(int& nd){
if(nd == -1)nd = get();
//cout << nd << endl;
}
inline ll eval(pll p,ll x){
return p.ff*x+ p.ss;
}
inline double intersect(pll p1,pll p2){
return (p1.ss-p2.ss)*1.0/(p2.ff-p1.ff);
}
void update(int& node,int ss,int se,pll ln){
expand(node);
if(ss == se){
if(eval(ln,ss) < eval(B[node].p,ss)){
B[node].p = ln;
}
return;
}
ll v1 = eval(ln,ss);
ll v2 = eval(ln,se);
ll v3 = eval(B[node].p,ss);
ll v4 = eval(B[node].p,se);
if(v1 <= v3 and v2 <= v4){
B[node].p = ln;
return;
}else if(v3 <= v1 and v4 <= v2){
return;
}
int mid = (ss+se)/2;
update(B[node].left,ss,mid,ln);
update(B[node].right,mid+1,se,ln);
}
ll query(int node,int ss,int se,int i){
if(node == -1) return INF;
if(i > se or i < ss)return INF;
if(ss == se){
return eval(B[node].p,i);
}
int mid = (ss+se)/2;
return min(min(eval(B[node].p,i),query(B[node].left,ss,mid,i)),query(B[node].right,mid+1,se,i));
}
public :
Segtree(){
PTR=0;
head = get();
// cout << head << endl;
}
inline void addLine(ll m,ll c){
update(head,0,1e6+1,{m,c});
}
inline ll query(ll x){
return query(head,0,1e6+1,x);
}
};
ll dp[50*1000+1][2];
//int opt[50*1000+1][2];
//Segtree ds[50*1000+1];
void computeDp(int k){
// cout << "e" << endl;
int n = all.size();
k = min(n,k);
FOR(i,n+1)dp[i][0] = INF;
dp[0][0] = 0;
// cout << "j" << endl;
vector<pll> lns;
vector<ll> add;
//cout << "d" << endl;
FOR(i,n){
add.pb(all[i].ss*all[i].ss + 1 + 2*all[i].ss);
}
ll E[n];
FOR(i,n)E[i] = all[t-1].ff*all[t-1].ff - 2*all[t-1].ff;
//cout << "e" << endl;
FOR(j,k+1){
if(j == 0)continue;
dp[0][1] = 0;
//cout << " e" << endl;
Segtree ds;
//cout << "d" << endl;
FORE(t,1,n){
ds.addLine((-2*all[t-1].ff),(dp[t-1][0] - C1[t-1] + E[t-1]));
}
for(int i = n;i>=1;i--){
//ll add =
ll mn = ds.query(all[i-1].ss);
dp[i][1] = mn + add[i-1];
continue;
}
FOR(i,n)dp[i][0] = dp[i][1];
}
}
ll take_photos(int n,int m,int k,vi r,vi c){
all = reduceList(createRanges(r,c,n));
prec();
//for(auto e:all)cout << e.ff<< ";"<<e.ss << endl;
computeDp(k);/*
FOR(i,min((int)all.size(),k)+1){
FOR(j,all.size()+1){
cout << dp[i][j] << " ";
};cout << endl;}*/
return dp[all.size()][1];
//return 0;
}
/*
int main(){
//int a[2] = {2,4,4,4,4};
//int b[2] = {3,5,6,5,6};
vi a;
vi b;
a.pb(1);a.pb(4);
b.pb(6);b.pb(7);
cout << take_photos(2,7,2,a,b) << endl;
return 0;
}
*/
Compilation message
aliens.cpp: In function 'void computeDp(int)':
aliens.cpp:193:24: error: 't' was not declared in this scope
FOR(i,n)E[i] = all[t-1].ff*all[t-1].ff - 2*all[t-1].ff;
^
