이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
int n;
vector <pair <__int128,__int128> > v;
struct Line{
mutable __int128 m,c,p;
bool operator<(const Line&o) const {
return m<o.m;
};
bool operator<(__int128 val) const {
return p<val;
};
};
struct LineContainer:multiset <Line,less<> > {
const __int128 inf=1e36;
__int128 div(__int128 a,__int128 b){
return a/b-((a^b)<0&&a%b);
}
bool intrs(iterator a,iterator b){
if (b==end()) return a->p=inf,0;
if (a->m==b->m) a->p=(a->c>b->c?inf:-inf);
else a->p=div(b->c-a->c,a->m-b->m);
return a->p>=b->p;
}
void addline(__int128 m,__int128 c){
auto z=insert({-m,-c,0});
auto a=z++;
auto b=a;
while (intrs(b,z)) z=erase(z);
if (a!=begin()&&intrs(--a,b)) intrs(a,b=erase(b));
while ((b=a)!=begin()&&(--a)->p>=b->p) intrs(a,erase(b));
}
__int128 query(__int128 val){
auto l=*lower_bound(val);
return -l.m*val-l.c;
}
};
const __int128 C=2e5;
__int128 dp[100010];
pair <long long,long long> calc(__int128 add){
LineContainer lc;
dp[0]=0;
lc.addline(C*-2*v[1].first,C*(v[1].first-1)*(v[1].first-1)+C*add+1);
for (int i=1; i<=n; i++){
dp[i]=lc.query(v[i].second)+C*v[i].second*(v[i].second+2);
if (i<n){
__int128 tp=max((__int128)0,v[i].second-v[i+1].first+1);
lc.addline(C*-2*v[i+1].first,dp[i]-C*tp*tp+C*(v[i+1].first-1)*(v[i+1].first-1)+C*add+1);
}
}
return {dp[n]/C-(dp[n]%C)*add,dp[n]%C};
}
long long take_photos(int N,int m,int k,vector <int> r,vector <int> c){
int til[m];
for (int i=0; i<m; i++) til[i]=i-1;
for (int i=0; i<N; i++){
int rr=r[i],cc=c[i];
if (rr>cc) swap(rr,cc);
til[rr]=max(til[rr],cc);
}
int mx=-1;
for (int i=0; i<m; i++){
if (til[i]>mx&&i<=til[i]){
v.push_back({i,til[i]});
mx=til[i];
}
}
n=v.size();
v.insert(v.begin(),{0,0});
long long L=0,R=1e12;
while (L<R){
long long mid=(L+R)/2;
if (calc(mid).second>k) L=mid+1;
else R=mid;
}
pair <long long,long long> cur=calc(L);
if (cur.second==k) return cur.first;
pair <long long,long long> nxt=calc(L-1);
if (nxt.second==cur.second) return cur.first;
return cur.first+(k-cur.second)*(nxt.first-cur.first)/(nxt.second-cur.second);
}
# | 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... |