This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
struct lr {
int l, r;
bool operator<(lr b) const { return l<b.l; }
};
struct point {
ll a, b;
ll operator()(ll x) const { return a*x+b; }
};
ll ccw(point& o, point& p, point& q) {
return (o.a-p.a)*(o.b-q.b)-(o.b-p.b)*(o.a-q.a);
}
ll pw(ll x) { return x*x; }
ll take_photos(int N, int M, int K, vector<int> L, vector<int> R) {
lr A[N+1];
for(int i=0; i<N; i++) {
int x=L[i], y=R[i];
A[i]={min(x, y), max(x, y)+1};
}
sort(A, A+N);
int N2=0;
for(int i=1; i<N; i++) if(A[N2].r<A[i].r)
A[N2+=A[N2].l<A[i].l]=A[i];
K=min(K, N=N2+1);
point H[N+1];
int D[N+1];
A[N].l=A[N-1].r;
auto f=[&](ll m, int k=INT_MAX) {
int s=0, e=0;
H[0]={-2*A[0].l, pw(A[0].l)};
D[0]=0;
for(int i=0; i<N; i++) {
ll l=A[i+1].l, r=A[i].r;
while(s<e && H[s](r)>H[s+1](r)) s++;
point p{-2*l, H[s](r) + pw(l)+pw(r)-pw(max(r-l, 0LL)) - m};
while(s<e && ccw(H[e-1], H[e], p)>=0) e--;
H[++e]=p;
D[e]=D[s]+1;
if(D[e]>k) return ll(-1);
}
return H[e].b-pw(A[N].l);
};
ll l=-pw(M), r=0;
while(l<r) {
ll m=l+r+1>>1;
if(~f(m, K)) l=m;
else r=m-1;
}
return f(r)+K*r;
}
Compilation message (stderr)
aliens.cpp: In function 'll take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:50:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
50 | ll m=l+r+1>>1;
| ~~~^~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |