#include "aliens.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define sz(x) ((int)x.size())
using namespace std;
#ifdef LOCAL
#define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) (__VA_ARGS__)
#define cerr if(0)cout
#endif
template<class TH> void _dbg(const char *sdbg, TH h){cerr<<sdbg<<"="<<h<<"\n";}
template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA...a){
while(*sdbg!=',')cerr<<*sdbg++;cerr<<"="<<h<<","; _dbg(sdbg+1, a...);
}
typedef long long ll;
struct point {
ll r,c;
bool operator<(const point& b)const {
return r==b.r?c>b.c:r<b.r;
}
};
// max cht
// cht.insert({a,b})
// cht.query(x)
struct CHT {
struct line {
ll first;
ll second;
ll count;
bool operator<(const line& b)const{
if(first==b.first) {
if(second==b.second)return count<b.count;
return second<b.second;
}
return first<b.first;
}
};
using frac=pair<ll,line>;
const ll INF=1e15;
set<line> ls;
set<frac> fs;
inline frac getf(line a,line b) {
if(b.fi>a.fi) return {(a.se-b.se)/(b.fi-a.fi)-((a.se-b.se)%(b.fi-a.fi)<0),b};
return {(b.se-a.se)/(a.fi-b.fi)-((b.se-a.se)%(a.fi-b.fi)<0),b};
}
void clear() {
ls.clear();fs.clear();
}
void addln(line ln) {
auto it=ls.lower_bound(ln);
if(it!=ls.end()) {
if(it==ls.begin()) fs.erase({-INF,*it});
else fs.erase(getf(*prev(it,1),*it));
fs.insert(getf(ln,*it));
}
if(it!=ls.begin())
fs.insert(getf(*prev(it,1),ln));
else fs.insert({-INF,ln});
ls.insert(ln);
}
set<line>::iterator removeln(set<line>::iterator it) {
if(it!=ls.begin())
fs.erase(getf(*prev(it,1),*it));
else fs.erase({-INF,*it});
if(next(it,1)!=ls.end()) {
fs.erase(getf(*it,*next(it,1)));
if(it!=ls.begin())
fs.insert(getf(*prev(it,1),*next(it,1)));
}
return ls.erase(it);
}
inline bool bad(line a,line b,line c) {
return getf(b,c)<=getf(a,b);
}
void insert(line newline) {
auto it=ls.lower_bound({newline.fi,-INF,0});
if(it!=ls.end()&&it->fi==newline.fi) {
if(it->se<newline.se) it=removeln(it);
else return;
}
if(it!=ls.end()&&it!=ls.begin()&&bad(*prev(it,1),newline,*it))
return;
if(it!=ls.begin()) {
auto jt=prev(it,1);
while(jt!=ls.begin()&&bad(*prev(jt,1),*jt,newline)) {
jt=removeln(jt);
jt--;
}
}
while(it!=ls.end()&&next(it,1)!=ls.end()&&bad(newline,*it,*next(it,1)))
it=removeln(it);
addln(newline);
}
pair<ll,ll> query(ll x) {
auto it=fs.lower_bound({x,{-INF,-INF,0}});
if(it==fs.begin()) return {-INF,0};
it--;
return {(it->se.fi)*x+(it->se.se),it->se.count};
}
}cht;
vector<point> v,tmp;
int n,m,k;
void add(ll a,ll b,ll c) {
cht.insert({-a,-b,c});
}
pair<ll,ll> query(ll x) {
pair<ll,ll> ret=cht.query(x);
return {-ret.fi,ret.se};
}
pair<ll,ll> f(ll x) {
int i;
pair<ll,ll> cur,pre;
cht.clear();
for(i=0;i<n;i++) {
ll a=-2*(v[i].r-1);
ll b=(v[i].r-1)*(v[i].r-1)+pre.fi+x;
ll c=pre.se;
if(i) {
b-=max((v[i-1].c-v[i].r+1)*(v[i-1].c-v[i].r+1),0ll);
}
add(a,b,c);
pair<ll,ll> r=query(v[i].c);
cur={r.fi+v[i].c*v[i].c,r.se+1};
pre=cur;
}
return cur;
}
long long take_photos(int n_, int m_, int k_, std::vector<int> r_, std::vector<int> c_) {
v.clear();tmp.clear();
n=n_,m=m_,k=k_;
int i,j;
for(i=0;i<n;i++) {
tmp.push_back({r_[i],c_[i]});
}
sort(tmp.begin(),tmp.end());
for(i=0,j=-1;i<n;i++) {
if(tmp[i].c>j) {
j=tmp[i].c;
v.push_back(tmp[i]);
}
}
n=sz(v);
ll lo=0,hi=1e15;
while(lo<hi) {
ll mid=(lo+hi)/2;
if(f(mid).se>k)lo=mid+1;
else hi=mid;
}
pair<ll,ll> ans=f(lo);
return ans.fi-ans.se*lo;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 4 |
| 2 |
Incorrect |
1 ms |
364 KB |
Wrong answer: output = 1, expected = 4 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 1 |
| 2 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 4 |
| 3 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 1 |
| 4 |
Correct |
1 ms |
492 KB |
Correct answer: answer = 5 |
| 5 |
Incorrect |
1 ms |
364 KB |
Wrong answer: output = 21, expected = 41 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 4 |
| 2 |
Incorrect |
1 ms |
364 KB |
Wrong answer: output = 1, expected = 4 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 4 |
| 2 |
Incorrect |
1 ms |
364 KB |
Wrong answer: output = 1, expected = 4 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 4 |
| 2 |
Incorrect |
1 ms |
364 KB |
Wrong answer: output = 1, expected = 4 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 4 |
| 2 |
Incorrect |
1 ms |
364 KB |
Wrong answer: output = 1, expected = 4 |
| 3 |
Halted |
0 ms |
0 KB |
- |
